《KKTgeometry从几何图形的角度来阐释KTT条件的意义课件》由会员分享，可在线阅读，更多相关《KKTgeometry从几何图形的角度来阐释KTT条件的意义课件（26页珍藏版）》请在金锄头文库上搜索。
1、MS&E 211December 1, 2005The Principles and Geometries of KKT and Optimization1KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: UnconstrainedProblem:Minimize f(x), where x is a vector that could have any values, positive or negativeFirst Order Necessary Condition (min or max
2、):f(x) = 0 (f/xi = 0 for all i) is the first order necessary condition for optimizationSecond 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 = 0xi
3、f2f/xi2 02KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Equality Constrained (one constraint)Problem:Minimize f(x), where x is a vectorSubject to: h(x) = bFirst Order Necessary Condition for minimum (or for maximum): f(x) = h(x) for some free ( is a scalar)Two surfaces m
4、ust be tangenth(x) = b and -h(x) = -b are the same;there is no sign restriction on h(x) = b3KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Equality Constrained (one constraint)First Order Necessary Condition: f(x) = h(x) for some Lagrangian:L(x, ) = f(x) - h(x)-b , Minimi
5、ze L(x, ) over x and Maximize L(x, ) over . Use principles of unconstrained optimizationL(x, ) = 0:xL(x, ) = f(x) - h(x) = 0L(x, ) = h(x)-b = 04KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Equality Constrained (multiple constraints)Problem:Minimize f(x), where x is a ve
6、ctorSuch that: hi(x) = bi for i = 1,2,mKKT Conditions (Necessary Conditions): Exist i ,i = 1,2,m, such thatf(x) = i=1n ihi(x) hi(x) = bi for i = 1,2,mSuch 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
7、(x) is convex and hi(x), i = 1,2,m, are linear.5KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Unconstrained, Except Non-Negativity ConditionProblem:Minimize f(x), where x is a vector, x 0 First Order Necessary Condition:f/xi = 0 if xi 0f/xi 0 if xi = 0Thus: f/xixi = 0 fo
8、r all xi, orf(x) x = 0, f(x) 0If interior point (x 0), then f(x) = 0 Nothing changes if the constraint is not bindingf/xi = 0xiff/xi 06KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometry of KKT: Inequality Constrained (one constraint)Problem:Minimize f(x), where x is a vectorSubject to:
9、 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 0If constraint is none-binding g(x) b, then f(x) =0 or = 07KKTgeometry(从几何图形的角度来
10、阐释KTT条件的意义)MS&E 211December 1, 2005Geometries 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 dir
11、ection of decreasing g(x).Thus -g(x) is perpendicular to the tangent hyperplane of g(x) = b at x.x1x2 -g(x)g (x) b8KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (one constraint)f(x) is similarly a vector perpendicular to the level set of f(x) evalu
12、ated 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.x1x2f(x) = c (constant)-f(x)9KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (one const
13、raint)First Order Necessary Condition: f(x) = g(x) for some 0 ( is a scalar)If constraint is binding g(x) = b then 0x1x2g(x) bf(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
14、10KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (one constraint)If -g(x) and -f(x) are not parallel, there are feasible points with less f(x).x1x2g(x) bf(x) constant-g(x)-f(x)11KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of K
15、KT: Inequality Constrained (one constraint)If -g(x) and -f(x) are parallel but in opposite direction, there are feasible points with less f(x).x1x2g(x) bf(x) constant-g(x)-f(x)12KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (one constraint)nFirst O
16、rder Necessary Condition: f(x) = 0 if constraint is not binding g(x) bX1X2f(x) decreases toward sink at the middle.At optimal point, f(x) = 0 This can be sees as an unconstrained optimum.13KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (one constrai
17、nt)First Order Necessary Condition: f(x) = g(x) for some 0 If constraint is non-binding g(x) 0 then = 0Lagrangian:L(x, ) = f(x) - g(x)-b , s.t. 0 Minimize L(x, ) over x and Maximize L(x, ) over . Use principles of unconstrained optimizationxL(x, ) = f(x) - g(x) = 0g(x)-b 0, then =0.14KKTgeometry(从几何
18、图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (one constraint)Problem:Mimimize f(x), where x is a vectorSubject to: g(x) bEquivalently: f(x) = g(x)g(x) b 0 g(x) b = 015KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrain
19、ed (two constraints)Problem:Minimize f(x), where x is a vectorSubject to: g1(x) b1 and g2(x) b2First 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) b22 = 0 1 g1(x) - b1 = 02 g2(x) - b2 = 0Shaded area is feasible set wi
20、th two constraintsx1x2-g1(x)-g2(x)-f(x)Both constraints are binding16KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (two constraints)Problem:Minimize f(x), where x is a vectorSubject to: g1(x) b1 and g2(x) b2First Order Necessary Conditions: f(x) =
21、1 g1(x), 1 0g2(x) b22 = 0 g1(x) - b1 = 0Shaded area is feasible set with two constraintsx1x2-g1(x)-f(x)First constraint is binding17KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (two constraints)Problem:Minimize f(x), where x is a vectorSubject to:
22、 g1(x) b1 and g2(x) b2First Order Necessary Conditions: f(x) = 0g1(x) b1 1 = 0 g2(x) b22 = 0 Shaded area is feasible set with two constraintsx1x2f(x)=0None constraint is binding18KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Geometries of KKT: Inequality Constrained (two constraints)Lagran
23、gian: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 maximizationL(x, 1, 2) = 0 (gradient with respect to x only)L(x, 1, 2) = f(x) - 1 g1(x) - 2 g2(x) = 0Thus f(x) = 1 g1(x) + 2 g2(x) Maximize L(x, 1, 2) over 1 0, 2 0.g1(x)-b1 0, then 1=0g2(x)-
24、b2 0, then 2=019KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005KKT: Inequality Constrained (multiple constraints)20KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005KKT Conditions: Inequality CasenThe Karush-Kuhn-Tucker Theorem: If the function f(x) has a minimum at x* in the feasible
25、 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*) = 0i 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
26、(as we have assumed here) we are dealing with a convex programming problem21KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Example: KKT Conditions22KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Example: KKT Conditions-f(x)g(x)The curve (surface) of the objective function is tangen
27、tial to the constraint curve (surface) at the optimal point. 23KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Example: Computation of the KKT ConditionIf = 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
28、 x1() and x2() into the constraint with equality gives us = 1.8.We can then solve for x1 = .61 and x2 = 1.28. 24KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005Economical Interpretation of Lagrange MultipliersAs with LPs, there is actually a whole area of duality theory that corresponds to N
29、LPs.In this vein, we can view Lagrangians as shadow prices for the constraints in NLP (corresponding to the y vector in LP)25KKTgeometry(从几何图形的角度来阐释KTT条件的意义)MS&E 211December 1, 2005KKT Conditions: Final NotesKKT conditions may not lead directly to a very efficient algorithm for solving NLPs. However
30、, they do have a number of benefits:They give insight into what optimal solutions to NLPs look likeThey provide a way to set up and solve small problemsThey provide a method to check solutions to large problemsThe Lagrange multipliers can be seen as shadow prices of the constraints26KKTgeometry(从几何图形的角度来阐释KTT条件的意义)
