`Lecture 26 Constrained Nonlinear Problems Necessary KKT Optimality ConditionsNovember 18, 2009Lecture 26Outline· Necessary Optimality Conditions for Constrained Problems · Karush-Kuhn-Tucker (KKT) optimality conditionsEquality constrained problems Inequality and equality constrained problems· Convex Inequality Constrained ProblemsSufficient optimality conditions· The material is in Chapter 18 of the book · Section 18.1.1 · Lagrangian Method in Section 18.2 (see 18.2.1 and 18.2.2) William Karush develop these conditions in 1939 as a part of his M.S. thesis at the University of Chicago; the same were developed independently later in 1951 by Harold W. Kuhn and Albert W. Tucker.Operations Research Methods1Lecture 26Constrained OptimizationLet f : Rn  R, gj : Rn  R for j = 1, . . . , m, and h : Rn  R for = 1, . . . , r Unconstrained NLP problem minimize f (x) no restrictions x  Rn Constrained NLP problem minimize f (x) subject to gj (x)  0, j = 1, . . . , m h (x) = 0, = 1, . . . , rFor constrained problem, we say that x if feasible if it satisfies all the constraints of the problem, i.e.,gj (x)  0, j = 1, . . . , m, h (x) = 0, = 1, . . . , rOperations Research Methods2Lecture 26Graphical IllustrationsThe set of all feasible points constitute the feasible region of the problemOperations Research Methods 3Lecture 26Operations Research Methods4Lecture 26EXAMPLE of Constrained NLP: Portfolio Selection with Risky Securitiesnnminimize V (x) =i=1 j=1 nij xixjsubject toj=1 npj xj  B µ j xj  Lj=1xj  0for all jThis is a constrained NLP problem. In fact it is linearly constrained.Operations Research Methods5Lecture 26Minimization vs MaximizationWe will focus on minimization type problems, since maximization problems can be transformed to minimization problems The optimal solutions (if any exist) of the problem maximize f (x) subject to gj (x)  0, j = 1, . . . , m h (x) = 0, = 1, . . . , r coincide with the optimal solutions of the following problem minimize -f (x) subject to gj (x)  0, j = 1, . . . , m h (x) = 0, = 1, . . . , rOperations Research Methods 6(1)(2)Lecture 26NOTE: The optimal values of the problems (1) and (2) are obviously not the same (differ in sign) Furthermore, the local maxima of problem (1) coincide with the local minima of problem (2).Operations Research Methods7Lecture 26Necessary Optimality ConditionsLet f : Rn  R be continuously differentiable over Rn Let each gj : Rn  R and each h : Rn  R. Unconstrained NLP problem minimize f (x) no restrictions x  Rn Necessary Optimality Condition: If x is an optimal solution for the problem, then x satisfiesf (x) = 0Operations Research Methods 8Constrained NLP problem minimize f (x) subject to gj (x)  0, j = 1, . . . , m h (x) = 0, = 1, . . . , r Necessary Optimality Condition: ???Lecture 26Necessary Optimality Conditions: Equality Constrained ProblemsConsider the equality constrained problem: minimize f (x) subject to h (x) = 0,= 1, . . . , r(3)The functions f and all h are continuously differentiable over Rn. The optimality conditions are specified through the use of Lagrangian Function:· Introduce a multiplier (shadow price)  for each constraint h (x) = 0. · Lagrangian Function is given byrL(x, ) = f (x) +=1 h (x)where  = (1, . . . , r )Operations Research Methods 9Lecture 26Necessary Optimality Condition: Assuming some regularity conditions for problem (3), if x is an optimal solution of the problem, then there exists a Lagrange multiplier (optimal shadow price)  = ( , . . . , ) such that 1 r         x L(x ,  ) = 0       f (x ) +r  =1  h (x ) = 0     L(x ,  ) = 0      h (x) = 0for= 1, . . . , r   is the optimal shadow price associated with the solution x This condition is known as KKT condition IMPORTANT: The KKT condition can be satisfied at a local minimum, a global minimum (solution of the problem) as well as at a saddle point. Question: We want to determine the optimal solutions of the problem (global minima of the constrained problem)? How can we use the KKT condition?Operations Research Methods 10Lecture 26Answer: We can set up a system of linear equations using the KKT condition:f (x) + r=1  h (x) = 0 h (x) = 0 for = 1, . . . , rWe have n + r unknown variables (x of size n and  of size r) and n + r equations We can solve the system and find the points that satisfy the equations (KKT condition) These points are known as stationary points (or KKT points) The optimal solutions (if any) are among these points.Operations Research Methods11Lecture 26NOTE: We need additional information to characterize the stationary points as global or local minimum or other by using the second order information for the objective f (x) at the KKT points (see Lecture 25).Operations Research Methods12Lecture 26ExampleDetermine all the stationary points of the following constrained problemminimize subject tof (x) = x2 + x2 + x2 1 2 3 x1 + x2 + 3x3 - 2 = 0 5x1 + 2x2 + x3 - 5 = 0We construct the Lagrangian function for the problem:L(x, ) = x2 +x2 +x2 +1(x1 +x2 +3x3 -2)+2(5x1 +2x2 +x3 -5) 1 2 3Operations Research Methods13Lecture 26We set up the equations:L(x, ) x1 L(x, ) x2 L(x, ) x3 L(x, ) 1 L(x, ) 2 = 2x1 + 1 + 52 = 0 = 2x2 + 1 + 22 = 0 = 2x3 + 31 + 2 = 0 = x1 + x2 + 3x3 - 2 = 0 = 5x1 + 2x2 + x3 - 5 = 0We solve them: x = [0.8043 0.3478 0.2826]T and  = -[0.0870 0.3044]T So we have only one KKT point, namely x = [0.8043 0.3478 0.2826]T - but we still do not know if this is optimal or notOperations Research Methods 14Lecture 26We can check the Hessian of f . We will find that the Hessian is given by a diagonal matrix with diagonal entries equal to 2. The Hessian is positive definite, therefore the point x is a global minimum.Operations Research Methods15Lecture 26Necessary Optimality Conditions: Inequality and Equality Constrained ProblemsConsider the following constrained problem: minimize f (x) subject to gj (x)  0, j = 1, . . . , m h (x) = 0, = 1, . . . , r(4)The functions f and all gj and h are continuously differentiable over Rn. The optimality conditions are specified through the use of Lagrangian Function:· Introduce a multiplier (shadow price) per constraint: µj  0 for each constraint gj (x)  0 and  for each constraint h (x) = 0Operations Research Methods 16Lecture 26· Lagrangian Function is given bym rL(x, µ, ) = f (x) +j=1µj gj (x) +=1 h (x)where µ = (µ1, . . . , µm) and  = (1, . . . , r )Operations Research Methods17Lecture 26Necessary Optimality Condition: Assuming some regularity conditions for problem (4), if x is an optimal solution of the problem, then there exist Lagrange multipliers (optimal shadow prices) µ = (µ , . . . , µ )  0 and  = ( , . . . , ) such that 1 m 1 rf (x) + gj (x)  0m  j=1 µjgj (x) +r  =1 h (x) = 0for all j = 1, . . . , m= 1, . . . , rh (x) = 0 for all µ  0 jfor all j = 1, . . . , m for all j = 1, . . . , mµgj (x) = 0 jµ and  is the optimal shadow price associated with the solution xThis is the KKT conditionOperations Research Methods 18Lecture 26Graphical Illustration of the KKT ConditionOperations Research Methods19Lecture 26IMPORTANT: The KKT condition can be satisfied at a local minimum, a global minimum (solution of the problem) as well as at a saddle point. We can use the KKT condition to characterize all the stationary points of the problem, and then perform some additional testing to determine the optimal solutions of the problem (global minima of the constrained problem).Operations Research Methods20Lecture 26Determining KKT points: we set up a KKT system for problem (4):f (x) + gj (x)  0m j=1 µjgj (x) +r =1 h (x) = 0for all j = 1, . . . , m= 1, . . . , rh (x) = 0 for all µj  0for all j = 1, . . . , m for all j = 1, . . . , m complementarity slacknessµj gj (x) = 0We may solve this (nonlinear) system in unknown variables x, µ and , and find all the points satisfying the KKT condition These points are stationary points (or KKT points) of the problemOperations Research Methods21Lecture 26The optimal points are among the KKT points We need additional information to characterize the KKT points as global or local minimum or other - we use the second order information, as discussed in Lecture 25.Operations Research Methods22Lecture 26Sufficient Optimality Conditions: Convex Inequality Constrained ProblemsConsider the following constrained problem: minimize f (x) subject to gj (x)  0, j = 1, . . . , m(5)Functions f and all gj are convex and continuously differentiable over Rn. We say that the problem is convex For this convex problem, the KKT conditions are also sufficient for optimality.Operations Research Methods23Lecture 26Sufficient Optimality Condition: Assuming some additional regularity conditions for convex problem (5), x is an optimal solution of the problem, if and only if there exists a Lagrange multiplier (optimal shadow price) µ = (µ , . . . , µ ) such that 1 mf (x) + gj (x)  0 µ  0 jm  j=1 µjgj (x)for all j = 1, . . . , mfor all j = 1, . . . , m for all j = 1, . . . , mµgj (x) = 0 jµ is the optimal shadow price associated with the solution xWe can use the KKT condition to fully recover optimal solutions of the convex problem (global minima of the constrained problem).Operations Research Methods24Lecture 26Looking for the solutions: we set up a KKT system for problem (5),f (x) + gj (x)  0m j=1 µjgj (x) +r =1 h (x) = 0for all j = 1, . . . , m= 1, . . . , rh (x) = 0 for all µj  0for all j = 1, . . . , m for all j = 1, . . . , m complementarity slacknessµj gj (x) = 0We solve this system in unknown variables x and µ, and find all the KKT points IMPORTANT By the assumed convexity of problem (5), all the KKT points are global minima of the problem (optimal solutions).Operations Research Methods 25Lecture 26EXAMPLEConsider the following problem minimize subject tof (x) = - ln(x1 + 1) - x2 2x1 + x2  3 x1  0 x2  0Operations Research Methods26`

#### Information

27 pages

Find more like this

#### Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

486775

### You might also be interested in

BETA
NotesPh567
Microsoft Word - Training Calendar Format 2nd quarter Dec 10 Jan Feb 11 no MF #.doc
PII: S0965-8564(98)00024-X