2 098 6 255 15 093 Recitation 10 Michael Frankovich and Shubham Gupta December 4 2009 1 Karush Kuhn Tucker Necessary Conditions P min s t f x gj x hi x 0 j 1 p 0 i 1 m Theorem KKT Necessary Conditions for Optimality If x is local minimum of P and the following Constraint Quali cation Condition CQC holds The vectors gj x j I x and hi x i 1 m are linearly indepen dent where I x j gj x 0 is the set of indices corresponding to active constraints at x Then there exist vectors u v s t 1 f x p uj gj x j 1 m vi hi x 0 i 1 2 uj 0 j 1 p 3 uj gj x 0 j 1 p or equivalently gj x 0 uj 0 j 1 p Theorem KKT Slater If x is local minimum of P and the following Slater Condition holds There exists some feasible solution x such that gj x 0 j I x where I x j gj x 0 is the set of indices corresponding to active constraints at x Then there exist vectors u v s t 1 f x p uj gj x j 1 m vi hi x 0 i 1 2 uj 0 j 1 p 1 3 uj gj x 0 j 1 p or equivalently gj x 0 uj 0 j 1 p Example Solve min x21 x22 x23 s t x1 x2 x3 18 Solution For some x to be a local minimum condition 1 requires that u s t 2xi u 0 i 1 2 3 Now the constraint can either be active or inactive If it is inactive then u 0 by condition 3 This would imply x1 x2 x3 0 but x 0 0 0 is infeasible so this cannot be true of a local minimum If it is active then x1 x2 x3 18 and 2xi u 0 i 1 2 3 This is a system of four linear equations in four unknowns We solve and obtain u 12 x 6 6 6 Since u 12 0 there exists a u as desired To check the regularity requirement we simply con rm that x 1 1 1 0 Also we could have checked that the Slater condition is satis ed eg use x 10 10 10 Hence 6 6 6 is the only candidate for a local minimum Now the question is is it a local minimum Note that since this is the unique candidate this is the same as asking if the function has a local minimum over the set Observe that the objective function is convex Why Because it is a positive combina tion of convex functions Now is the feasible set convex Answer yes since it is of the form x Rn f x 0 where f is a convex function So we may apply a stronger version of the KKT condtions the KKT su cient condi tions which imply that any x which satis es the KKT necessary conditions and also meets these two convexity requirements is in fact a global minimum So the point x 6 6 6 is the unique global minimum unique since it was the only candidate Example 1 Solve min log x1 1 x2 s t g x 2x1 x2 3 0 x1 x2 0 1 Thanks to Andy Sun 2 Solution Firstly observe that this is a convex optimization problem since f x is convex a pos itive combination of the convex functions x2 and log x1 1 and the constraint functions g x x1 and x2 are convex again this is required for the feasible space to be convex since we have constraints Alternatively in this case we can see that the feasible space is a polyhedron which we know to be convex Now in order to use KKT we need to assume which inequalities are active Let s start by assuming at a local minimum x only g x 0 is active This leads to the 1 that 2 system x1 1 u 0 which gives u 1 and x1 0 5 which is not feasible so 1 1 our assumption cannot be correct 1 2 x 1 Now try assuming g x 0 and x1 0 are active giving the system 1 u1 1 1 1 0 which gives u1 1 u2 1 and x2 3 recall we assumed x1 0 u2 0 Now since it s a convex optimization problem and the Slater condition is trivially satis ed this is a global minimum by the KKT su cient conditions Example The following example shows that the KKT theorem may not hold if the regularity condition is violated Consider min s t x1 x2 x1 1 x22 1 x1 3 2 x22 9 2 0 0 The feasible region is the intersection of two circles one centered at the point 1 0 with radius 1 the other at the point 3 0 with radius 3 The intersection occurs at the origin which is the optimal solution by inspection We have f x 1 1 h1 x 2x1 2 2x2 2 0 and h1 x 2x1 6 2x2 6 0 So condition 1 cannot hold Conjugate Gradient Method2 2 Consider minimizing the quadratic function f x 21 x Qx c x 1 d1 d2 dm are Q conjugate if d j i Qdj 0 i 2 Thanks to Allison Chang for notes 3 2 Let x0 be our initial point 3 Direction d1 f x0 4 Direction dk 1 f xk 1 k dk where k f xk 1 dk d k Qdk in the quadratic 2 xk 1 case and k f in the general case It turns out that with each dk f xk 2 constructed in this way d1 d2 dk are Q conjugate 5 By Expanding Subspace Theorem xk 1 minimizes f x over the a ne subspace S x0 span d1 d2 dk 6 Hence nite convergence n steps 3 Barrier Methods A barrier function G x is a continuous function with the propertiy that it approaches as one of the gj x approaches 0 from below Examples p log gj x and p j 1 j 1 1 gj x Consider the primal dual pair of linear optimization problems P min s t s t c x Ax x D b 0 max b p s t A p s s t s c 0 To solve P we de ne the following barrier problem BP min B x c x s t Ax b n j 1 log xj Assume that for all 0 BP has an optimal solution x This optimum will be unique Why As varies the x form what is called the central path Theorem lim 0 x exists and x lim 0 x is an optimal solution to P Then the barrier problem from the dual problem is BD max b p nj 1 log sj s t A p s c 4 Theorem Let 0 Then x s p are optimal solutions to BP and BD if and only if the following …