Nonlinear Programming: Concepts, Algorithms and Applications

1 Nonlinear Programming: Concepts, Algorithms and ApplicationsL. T. BieglerChemical Engineering DepartmentCarnegie Mellon UniversityPittsburgh, PA 2 IntroductionUnconstrained Optimization Algorithms Newton Methods Quasi-Newton MethodsConstrained Optimization Karush Kuhn-Tucker Conditions Special Classes of Optimization Problems Reduced Gradient Methods (GRG2, CONOPT, MINOS) Successive Quadratic Programming (SQP) Interior Point MethodsProcess Optimization Black Box Optimization Modular Flowsheet Optimization Infeasible Path The Role of Exact DerivativesLarge-Scale Nonlinear Programming Data Reconciliation Real-time Process OptimizationFurther Applications Sensitivity Analysis for NLP Solutions Multiperiod Optimization ProblemsSummary and ConclusionsNonlinear Programming and Process Optimization3 IntroductionOptimization: given a system or process, find the best solution to this process within Function.

2 Indicator of "goodness" of solution, , cost, yield, profit, : variables that influence process behavior and can be adjusted for many cases, this task is done by trial and error (through case study). Here, we are interested in a systematicapproach to this task - and to make this task as efficient as related areas:- Math programming- Operations ResearchCurrently - Over 30 journals devoted to optimization with roughly 200 papers/month - a fast moving field!4 Optimization ViewpointsMathematician- characterization of theoretical properties of optimization, convergence, existence, local convergence Analyst- implementation of optimization method for efficient and "practical" use. Concerned with ease of computations, numerical stability, applies optimization method to real problems. Concerned with reliability, robustness, efficiency, diagnosis, and recovery from LiteratureEngineering1.

3 Edgar, , Himmelblau, and L. S. Lasdon, Optimization of Chemical Processes, McGraw-Hill, Papalambros, P. and D. Wilde, Principles of Optimal Design. Cambridge Press, Reklaitis, G., A. Ravindran, and K. Ragsdell, Engineering Optimization, Wiley, Biegler, L. T., I. E. Grossmann and A. Westerberg, Systematic Methods of Chemical Process Design, prentice hall , Analysis1. Dennis, and R. Schnabel, Numerical Methods of Unconstrained Optimization, prentice - hall , (1983), SIAM (1995)2. Fletcher, R. Practical Methods of Optimization,Wiley, Gill, , W. Murray and M. Wright, Practical Optimization, Academic Press, 1981. 4. Nocedal, J. and S. Wright, Numerical Optimization, Springer, 19986 Scope of optimizationProvide systematic frameworkfor searching among a specified space of alternativesto identify an optimal design, , as a decision-making toolPremiseConceptual formulation of optimal product and process design corresponds to a mathematical programmingproblemnynyRxyxgyxhstyxf}1 ,0{0),(0),(),(min =Motivation7xxHybridxxNonlinear MPCxLinear MPCxxReal-time optimizationxxxSupply ChainxxxxSchedulingxxFlowsheetingxxx Equipment Designx xxxReactorsxxSeparationsxxxxxxMENS xxxxxxHENSSA/GANLPLP,QPGlobalMINLPMILPO ptimization in Design, Operations and Control8 Unconstrained Multivariable OptimizationProblem:Min f(x)(nvariables)Equivalent to:Max -f(x), x RnNonsmooth Functions- Direct Search Methods- Statistical/Random MethodsSmooth Functions- 1st Order Methods-Newton Type Methods- Conjugate Gradients9 Example.

4 Optimal Vessel DimensionsMin TC 2 D2 + S C DL = cost V - 2 D L4 = 0 Min TC 2 D2 + S C4VD = cost d(cost)dD = TC D - s4VC2D = 0D = 4V SCTC 1/3 L =4V 1/3 TCSC 2/3 What is the optimal L/D ratio for a cylindrical vessel?Constrained Problem(1)Convert to Unconstrained (Eliminate L)(2)==> L/D = CT/CSNote:-What if L cannot be eliminated in (1) explicitly? (strange shape)-What if D cannot be extracted from (2)? (cost correlation implicit)10 Two Dimensional Contours of F(x)Convex FunctionNonconvex FunctionMultimodal, NonconvexDiscontinuousNondifferentiable (convex)11 Local vs. Global Solutions Find a local minimumpoint x* for f(x) for feasible region defined by constraint functions: f(x*) f(x) for all x satisfying the constraints in some neighborhood around x* (not for all x X) Finding and verifying global solutionswill not be considered here.

5 Requires a more expensive search ( spatial branch and bound). A local solution to the NLP is also a global solution under the following sufficient conditions based on convexity. f(x)is convex in domain X, if and only if it satisfies:f( y + (1- ) z) f(y) + (1- )f(z)for any , 0 1, at all points yand zin X. 12 Linear algebra - BackgroundSome Definitions Scalars - Greek letters, , , Vectors - Roman Letters, lower case Matrices - Roman Letters, upper case Matrix Multiplication:C = A B if A n x m, B m x pand C n x p, Cij= kAikBkj Transpose - if A n x m, interchange rows and columns --> AT m x n Symmetric Matrix - A n x n(square matrix) and A = AT Identity Matrix - I, square matrix with ones on diagonal and zeroes elsewhere. Determinant: "Inverse Volume" measure of a square matrixdet(A) = i(-1)i+jAijAijfor any j, or det(A) = j(-1)i+jAijAijfor any i, where Aijis the determinantof an order n-1matrix with row i and column j removed.

6 Det(I) = 1 Singular Matrix: det (A) = 013 f = f/1 x f/2 x.. f/n x 2 f ( x) = 2 f12 x 2 f1 x2 x 2 f1 xn x ..2 fn x1 x 2 fn x2 x 2 fn2 x 2 f xj xi2 fj xi xGradient Vector- ( f(x))Hessian Matrix( 2f(x) - Symmetric)Note: = Linear algebra - Background14 Some Identities for Determinantdet(A B) = det(A) det(B);det (A) = det(AT)det( A) = ndet(A); det(A) = i i(A) Eigenvalues:det(A- I) = 0, Eigenvector: Av = vCharacteristic values and directions of a nonsymmetric matrices eigenvalues can be complex, so we often use singular values, = (AT )1/2 0 Vector Norms|| x ||p= { i|xi|p}1/p(most common are p = 1, p = 2 (Euclidean) and p = (max norm = maxi|xi|)) Matrix Norms||A|| = max ||A x||/||x|| over x (for p-norms)||A||1- max column sum of A, maxj( i|Aij|)||A|| - maximum row sum of A, maxi( j|Aij|)||A||2= [ max( )](spectral radius)||A||F= [ i j(Aij)2]1/2 (Frobenius norm) ( ) = ||A|| ||A-1|| (condition number) = max/ min(using 2-norm)Linear algebra - Background15 Find v and where Avi= ivi, i = i,nNote: Av - v = (A - I) v = 0 or det (A - I) = 0 For this relation is an eigenvalueand v is an eigenvectorof A is symmetric, all iare real i> 0, i = 1, n; A is positivedefinite i< 0, i = 1, n.

7 A is negativedefinite i= 0, some i: A is singularQuadraticFormcan be expressed in CanonicalForm(Eigenvalue/Eigenvector)xTA x A V = V V - eigenvector matrix (n x n) - eigenvalue (diagonal) matrix = diag( i)If A is symmetric, all iare realand V can be chosen orthonormal(V-1= VT). Thus, A = V V-1= V VTFor QuadraticFunction: Q(x) = aTx + xTAxDefine:z = VTx and Q(Vz) = (aTV) z + zT(VTAV)z= (aTV) z + zT zMinimumoccurs at (if i> 0) x = -A-1a orx = Vz = -V( -1 VTa)Linear algebra - Eigenvalues16 Positive (or Negative) CurvaturePositive (or Negative) Definite HessianBoth eigenvalues are strictly positive or negative A is positive definiteor negative definite Stationary points are minima or maxima17 Zero Curvature Singular HessianOne eigenvalue is zero, the other is strictly positive or negative A is positive semidefiniteor negative semidefinite There is a ridge of stationary points (minima or maxima)18 One eigenvalue is positive, the other is negative Stationary point is a saddle point A is indefiniteNote.

8 These can also be viewed as two dimensional projections for higher dimensional problemsIndefinite Curvature Indefinite Hessian19 Eigenvalue ExampleMin Q(x) =11 Tx+12xT2 11 2 x AV = V with A = 2 11 2 VTAV= =1 00 3 with V = 1/ 21/ 2-1/ 21/ 2 All eigenvalues are positive Minimum occurs at z* = -G-1 VTaz=VTx=(x1 x2) / 2(x1+x2) / 2 x=Vz=(x1+x2) / 2( x1+x2) / 2 z*=02 /(3 2) x*=1/ 31/ 3 201. Convergence Theory Global Convergence - will it converge to a local optimum (or stationary point) from a poor starting point? Local Convergence Rate - how fast will it converge close to the solution? 2. Benchmarks on Large Class of Test ProblemsRepresentative Problem (Hughes, 1981)Min f(x1, x2) = exp(- )u = x1- = x2- (a1+ a2u2(1- u)1/2 - a3u) = -b1+ b2u2 (1+u)1/2 + b3u = c1v2(1 - c2v)/(1+ c3u2)a = [ , , ]b = [5, 26, 3]c = [40, 1, 10]x* = [ , ]f(x*) = of Optimization Methods21 Three Dimensional Surface and Curvature for Representative Test ProblemRegions where minimum eigenvalue is less than:[0, -10, -50, -100, -150, -200]22 What conditions characterize an optimal solution?

9 X1x2x*Contours of f(x)Unconstrained Local MinimumNecessary Conditions f (x*) = 0pT 2f (x*) p 0 for p n(positive semi-definite)Unconstrained Local MinimumSufficient Conditions f (x*) = 0pT 2f (x*) p > 0 for p n(positive definite)Since f(x*) = 0, f(x)is purelyquadraticfor xclose to x**)*)((*)(21*)(*)(*)()(2xxxfxxxxxfxfxfT T + +=For smooth functions, why are contours around optimum elliptical?Taylor Seriesin n dimensions about x*:23 Taylor Series for f(x)about xkTake derivative wrt x, set LHS 00 f(x) = f(xk) + 2f(xk) (x - xk) (x - xk) d = - ( 2f(xk))-1 f(xk) f(x)is convex (concave) if for all x n, 2f(x)is positive (negative) minj j 0 (maxj j 0) Method can fail if:-x0far from optimum- 2fis singular at any point-f(x)is not smooth Search direction, d, requires solution of linear equations. Near solution: k +1x - x *= K kx - x * 2 Newton s Method240.

10 Guess x0, Evaluate f(x0).1. At xk, evaluate f(xk).2. Evaluate Bk= 2f(xk)or an Solve: Bkd = - f(xk)If convergence error is less than , || f(xk) || and ||d|| STOP, else go to 4. 4. Find so that 0 < 1 and f(xk+ d) < f(xk)sufficiently (Each trial requires evaluation of f(x)) +1= xk+ d. Set k = k + 1Go to Newton Algorithm - Line Search25 Newton s Method - Convergence PathStarting Points[ , ] needs steepest descent steps w/ line search up to O , takes 7 iterations to || f(x*)|| 10-6[ , ] converges in four iterations with full steps to || f(x*)|| 10-626 Choice of Bkdetermines Steepest Descent: Bk= I- Newton: Bk= 2f(x) With suitable Bk, performance may be good enough if f(xk+ d)is sufficiently decreased (instead of minimized along line search direction). Trust region extensionsto Newton's method provide very strong global convergence properties and very reliable Algorithms .