KKTgeometry(从几何图形的角度来阐释KTT条件的意义.ppt

1,The Principles and Geometries of KKT and Optimization,2,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/xi = 0 for all i) is the first order necessary condition for optimization Second Order Necessary Condition: 2f(x) is positive semidefinite (PSD) x 2f(x) x 0 for all x Second Order Sufficient Condition (Given FONC satisfied) 2f(x) is positive definite (PD) x 2f(x) x 0 for all x ,f/xi = 0,xi,f,3,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,4,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: xL(x, ) = f(x) - h(x) = 0 L(x, ) = h(x)-b = 0,5,Geometries of KKT: Equality Constrained (multiple constraints),Problem: Minimize f(x), where x is a vector Such that: hi(x) = bi for i = 1,2,m KKT Conditions (Necessary Conditions): Exist i ,i = 1,2,m, such that f(x) = i=1n ihi(x) hi(x) = bi 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 hi(x), i = 1,2,m, are linear.,6,Geometries of KKT: Unconstrained, Except Non-Negativity Condition,Problem: Minimize f(x), where x is a vector, x 0 First Order Necessary Condition: f/xi = 0 if xi 0 f/xi 0 if xi = 0 Thus: f/xixi = 0 for all xi, 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/xi = 0,xi,f,f/xi 0,7,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,8,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.,9,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.,x1,x2,f(x) = c (constant),-f(x),10,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,x1,x2,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,11,Geometries of KKT: Inequality Constrained (one constraint),If -g(x) and -f(x) are not parallel, there are feasible points with less f(x).,12,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).,x1,x2,g(x) b,f(x) constant,-g(x),-f(x),13,Geometries of KKT: Inequality Constrained (one constraint),First Order Necessary Condition: f(x) = 0 if constraint is not binding g(x) b,X1,X2,f(x) decreases toward sink at the middle. At optimal point, f(x) = 0 This can be sees as an unconstrained optimum.,14,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 xL(x, ) = f(x) - g(x) = 0 g(x)-b 0, then =0.,15,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,16,Geometries of KKT: Inequality Constrained (two constraints),Problem: Minimize f(x), where x is a vector Subject to: g1(x) b1 and g2(x) b2 First Order Necessary Conditions: f(x) = 1 g1(x) + 2 g2(x), 1 0, 2 0 f(x) lies in the cone between g1(x) and g2(x) g1(x) b1 1 = 0 g2(x) b2 2 = 0 1 g1(x) - b1 = 0 2 g2(x) - b2 = 0 Shaded area is feasible set with two constraints,x1,x2,-g1(x),-g2(x),-f(x),Both constraints are binding,17,Geometries of KKT: Inequality Constrained (two constraints),Problem: Minimize f(x), where x is a vector Subject to: g1(x) b1 and g2(x) b2 First Order Necessary Conditions: f(x) = 1 g1(x), 1 0 g2(x) b2 2 = 0 g1(x) - b1 = 0 Shaded area is feasible set with two constraints,x1,x2,-g1(x),-f(x),First constraint is binding,18,Geometries of KKT: Inequality Constrained (two constraints),Problem: Minimize f(x), where x is a vector Subject to: g1(x) b1 and g2(x) b2 First Order Necessary Conditions: f(x) = 0 g1(x) b1 1 = 0 g2(x) b2 2 = 0 Shaded area is feasible set with two constraints,x1,x2,f(x)=0,None constraint is binding,19,Geometries of KKT: Inequality Constrained (two constraints),Lagrangian: L(x, 1, 2) = f(x) - 1 g1(x)-b1 - 2 g2(x)-b2 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 g1(x) - 2 g2(x) = 0 Thus f(x) = 1 g1(x) + 2 g2(x) Maximize L(x, 1, 2) over 1 0, 2 0. g1(x)-b1 0, then 1=0 g2(x)-b2 0, then 2=0,20,KKT: Inequality Constrained (multiple constraints),21,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 gi(x*), i=1,2,m, exist, then there is an m-dimensional vector such that 0 f(x*)-i=1m igi(x*) = 0 i gi(x*) - bi = 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,22,Example: KKT Conditions,23,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.,24,Example: Computation of the KKT Condition,If = 0, then x1 = 0 and x2 = 0, and thus the constraint would not hold with equality. Therefore, must be positive. Plugging the two values of x1() and x2(