资源描述
*,*,Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,MS&E 211,December 1, 2005,The Principles and Geometries of KKT and Optimization,1,Geometries of KKT: Unconstrained,Problem:,Minimize f(x), where x is a vector that could have any values, positive or negative,First Order Necessary Condition (min or max),:,f(x) = 0 (f/x,i,= 0 for all i) is the first order necessary condition for optimization,Second Order Necessary Condition,:,2,f(x) is positive,semidefinite,(PSD), x,2,f(x),x,0 for all x ,Second Order Sufficient Condition,(Given FONC satisfied,),2,f(x) is positive definite (PD), x,2,f(x),x,0 for all x ,f/x,i,= 0,x,i,f,2,f/x,i,2, 0,2,Geometries of KKT: Equality Constrained (one constraint),Problem:,Minimize f(x), where x is a vector,Subject to:,h(x,),= b,First Order Necessary Condition,for minimum (or for maximum):,f(x) =, ,h(x,),for some,free (,is a scalar),Two surfaces must be tangent,h(x,),= b and -,h(x,),= -b are the same;,there is no sign restriction on,h(x),= b,3,Geometries of KKT: Equality Constrained (one constraint),First Order Necessary Condition:,f(x) =,h,(x,) for some,Lagrangian,:,L,(x,) =,f(x) -,h,(x)-b, ,Minimize,L,(x,) over x and,Maximize,L,(x,) over,. Use principles of unconstrained optimization,L,(x,) = 0,:,x,L,(x,) =,f(x) -,h,(x,) = 0,L,(x,) =,h,(x)-b,= 0,4,Geometries of KKT: Equality Constrained (multiple constraints),Problem:,Minimize f(x), where x is a vector,Such that:,h,i,(x,) = b,i,for i = 1,2,m,KKT Conditions (Necessary Conditions),: Exist,i,i = 1,2,m, such that,f(x) =,i=1,n,i,h,i,(x,),h,i,(x,) =,b,i,for i = 1,2,m,Such a point (x,) is called a,KKT point, and,is called the,Dual Vector,or the,Lagrange Multipliers,.,Furthermore, these conditions are sufficient if,f(x,) is convex and,h,i,(x,), i = 1,2,m,are linear.,5,Geometries of KKT: Unconstrained, Except Non-Negativity Condition,Problem:,Minimize f(x), where x is a vector, x,0,First Order Necessary Condition,:,f/x,i,= 0 if x,i, 0,f/x,i,0 if x,i,= 0,Thus: ,f/x,i,x,i,= 0 for all x,i, or,f(x),x = 0,f(x,),0,If interior point (x 0), then,f(x) = 0,Nothing changes if the constraint is not binding,f/x,i,= 0,x,i,f,f/x,i, 0,6,Geometry of KKT: Inequality Constrained (one constraint),Problem:,Minimize f(x), where x is a vector,Subject to:,g(x,),b.,Assume feasible set and set of points preferred to any point are all convex sets.,(i.e. convex program),First Order Necessary Condition,:,f(x) =, ,g(x,),for some,0 (,is a scalar),If constraint is binding ,g(x,),= b, then,0,If constraint is none-binding ,g(x,), b, then,f(x,) =0 or,= 0,7,Geometries of KKT: Inequality Constrained (one constraint),For any point x on the frontier of the feasible region of g(x),b, recall that -,g(x) is the direction of steepest descent of g(x) at x.,It is also perpendicular to the frontier of g(x) = b, pointing in the direction of decreasing g(x).,Thus -,g(x) is perpendicular to the tangent,hyperplane,of g(x) = b at x.,x,1,x,2,-,g(x),g,(x),b,8,Geometries of KKT: Inequality Constrained (one constraint),f(x) is similarly a vector perpendicular to the level set of f(x) evaluated at x:,Say f(x) = c. -,f(x) is a vector pointed in direction of decreasing value of f(x).,Also, -,f(x) is perpendicular to the tangent,hyperplane,of f(x) = c at x.,x,1,x,2,f(x) = c (constant),-,f(x),9,Geometries of KKT: Inequality Constrained (one constraint),First Order Necessary Condition:,f(x) =,g(x) for some,0 (,is a scalar),If constraint is binding ,g(x),= b then, 0,x,1,x,2,g(x),b,f(x) constant,-,f(x) is perpendicular to f(x) constant,-,g(x) is perpendicular to frontier: g(x) = b,-,g(x),At,optimum,-,g(x) and -,f(x) must be parallel: two surfaces must be tangent,10,Geometries of KKT: Inequality Constrained (one constraint),If -,g(x) and -,f(x) are not parallel, there are feasible points with less f(x).,x,1,x,2,g(x),b,f(x) constant,-,g(x),-,f(x),11,Geometries of KKT: Inequality Constrained (one constraint),If -,g(x) and -,f(x) are parallel but in opposite direction, there are feasible points with less f(x).,x,1,x,2,g(x),b,f(x) constant,-,g(x),-,f(x),12,Geometries of KKT: Inequality Constrained (one constraint),First Order Necessary Condition:,f(x) =,0 if constraint is not binding ,g(x) ,b,X,1,X,2,f(x) decreases toward sink at the middle.,At optimal point,f(x) =,0,This can be sees as an unconstrained optimum.,13,Geometries of KKT: Inequality Constrained (one constraint),First Order Necessary Condition:,f(x) =,g(x) for some,0,If constraint is non-binding ,g(x) ,0 then,= 0,Lagrangian,:,L,(x,) =,f(x) -,g(x)-b ,s.t,.,0,Minimize,L,(x,) over x and,Maximize,L,(x,) over,. Use principles of unconstrained optimization,x,L,(x,) =,f(x) -,g(x) = 0,g(x)-b, 0, then,=0.,14,Geometries of KKT: Inequality Constrained (one constraint),Problem:,Mimimize,f(x), where x is a vector,Subject to: g(x),b,Equivalently:,f(x) =,g(x),g(x),b,0,g(x) b,= 0,15,Geometries of KKT: Inequality Constrained (two constraints),Problem:,Minimize f(x), where x is a vector,Subject to: g,1,(x),b,1,and,g,2,(x),b,2,First Order Necessary Conditions,:,f(x) =,1,g,1,(x) +,2,g,2,(x),1,0,2,0,f(x) lies in the cone between,g,1,(x) and,g,2,(x),g,1,(x) ,b,1,1,=,0,g,2,(x) ,b,2,2,=,0,1,g,1,(x) -,b,1, = 0,2,g,2,(x) -,b,2, = 0,Shaded area is feasible,set with two constraints,x,1,x,2,-,g,1,(x),-,g,2,(x),-,f(x),Both constraints are binding,16,Geometries of KKT: Inequality Constrained (two constraints),Problem:,Minimize f(x), where x is a vector,Subject to: g,1,(x),b,1,and,g,2,(x),b,2,First Order Necessary Conditions,:,f(x) =,1,g,1,(x),1,0,g,2,(x) ,b,2,2,=,0,g,1,(x) -,b,1,= 0,Shaded area is feasible,set with two constraints,x,1,x,2,-,g,1,(x),-,f(x),First constraint is binding,17,Geometries of KKT: Inequality Constrained (two constraints),Problem:,Minimize f(x), where x is a vector,Subject to: g,1,(x),b,1,and,g,2,(x),b,2,First Order Necessary Conditions,:,f(x) =,0,g,1,(x) ,b,1,1,=,0,g,2,(x) ,b,2,2,=,0,Shaded area is feasible,set with two constraints,x,1,x,2,f(x)=0,None constraint is binding,18,Geometries of KKT: Inequality Constrained (two constraints),Lagrangian,:,L(x,1,2,) =,f(x) -,1,g,1,(x)-b,1, -,2,g,2,(x)-b,2,Minimize L(x,1,2,) over x.,Use principles of unconstrained maximization,L(x,1,2,) = 0 (gradient with respect to x only),L(x,1,2,) =,f(x) -,1,g,1,(x) -,2,g,2,(x) = 0,Thus,f(x) =,1,g,1,(x) +,2,g,2,(x),Maximize,L(x,1,2,) over,1,0,2,0.,g,1,(x)-b,1, 0, then,1,=0,g,2,(x)-b,2, 0, then,2,=0,19,KKT: Inequality Constrained (multiple constraints),20,KKT Conditions: Inequality Case,The Karush-Kuhn-Tucker Theorem:,If the function f(x) has a minimum at x* in the feasible set and if,f(x*) and,g,i,(x*), i=1,2,m, exist, then there is an m-dimensional vector,such that,0,f(x*)-,i=1,m,i,g,i,(x*) =,0,i,g,i,(x*) -,b,i,= 0, for i=1,2,m.,Such a point (x*,) is called a,KKT point, and,is called the,Dual Vector,or the,Lagrange Multipliers,.,Furthermore, these conditions are sufficient if (as we have assumed here) we are dealing with a convex programming problem,21,Example: KKT Conditions,22,Example: KKT Conditions,-,f(x),g(x),The curve (surface) of the objective function is tangential to the constraint curve (surface) at the optimal point.,23,Example: Computation of the KKT Condition,If,= 0, then x,1,= 0 and x,2,= 0, and thus the constraint would not hold with equality. Therefore,must be positive.,Plugging the two values of x,1,(,),and x,2,(,),into the constraint with equality gives us,= 1.8.,We can then solve for x,1,= .61 and x,2,= 1.28.,24,Economical Interpretation of Lagrange Multipliers,As with LPs, there is actually a whole area of duality theory that corresponds to,NLPs,.,In this vein, we can view,Lagrangians,as shadow prices for the constraints in NLP (corresponding to the y vector in LP),25,KKT Conditions: Final Notes,KKT conditions may not lead directly to a very efficient algorithm for solving,NLPs,. However, they do have a number of benefits:,They give insight into what optimal solutions to,NLPs,look like,They provide a way to set up and solve small problems,They provide a method to check solutions to large problems,The Lagrange multipliers can be seen as shadow prices of the constraints,26,
展开阅读全文