15 093 Optimization Methods Lecture 20 The Conjugate Gradient Algorithm Optimality conditions for constrained optimization 1 Outline Slide 1 1 The Conjugate Gradient Algorithm 2 Necessary Optimality Conditions 3 Su cient Optimality Conditions 4 Convex Optimization 5 Applications 2 2 1 The Conjugate Gradient Algorithm Quadratic functions 1 min f x x Qx c x 2 De nition d1 dn are Q conjugate if di 0 Slide 2 d i Qdj 0 i j Proposition If d1 dn are Q conjugate then d1 dn are linearly inde pendent 2 2 Motivation Slide 3 Given Q conjugate d1 dn and xk compute k min f xk dk c x c dk 1 k x dk Q xk dk 2 1 f xk f xk dk 2 d k Qdk 2 Solution k 2 3 f xk dk d k Qdk xk 1 xk k dk Expanding Subspace Theorem Slide 4 d1 dn are Q conjugate Then xk 1 solves min f x s t x x1 k j 1 Moreover xn 1 x 1 j dj 2 4 The Algorithm Slide 5 Step 0 Given x1 set k 1 d1 f x0 Step 1 For k 1 n do If f xk stop else k argmin f xk dk f xk dk d k Qdk xk 1 xk k dk dk 1 f xk 1 k dk 2 5 k f xk 1 Qdk d k Qdk Correctness Slide 6 Theorem The directions d1 dn are Q conjugate 2 6 Convergence Properties Slide 7 This is a nite algorithm If there are only k distinct eigenvalues of Q the CGA nds an optimal solution in k steps Idea of pre conditioning Consider min f Sx 1 Sx Q Sx c Sx 2 so that the number of distinct eigenvalues of S QS is small 2 7 Example Slide 8 f x 35 19 22 28 16 Q 3 16 6 4 4 19 43 33 19 5 2 5 4 0 0 22 33 40 29 12 7 6 2 2 4 28 19 29 39 16 7 14 6 2 4 16 5 12 16 12 4 8 2 4 8 3 2 7 7 4 5 1 0 1 4 1 x Qx c x 2 16 6 4 4 5 4 0 0 6 2 2 4 14 6 2 4 8 2 4 8 1 0 1 4 12 2 2 4 2 4 0 0 2 0 2 4 4 0 4 16 Q 17 641 1 0 0 3 0 and c 2 0 6 7 4 2 Q 1 Q 1 2 0 999774 Slide 9 2 8 k f xk f xk f x 1 2 3 4 5 6 7 8 9 10 11 12 12 000000 8 758578 1 869218 12 777374 30 479483 187 804367 309 836907 408 590428 754 887518 2567 158421 2581 711672 2581 726852 2593 726852 2590 485430 2583 596069 2568 949478 2551 247369 2393 922485 2271 889945 2173 136424 1826 839334 14 568431 0 015180 0 000000 f xk f x f xk 1 f x 1 000000 0 998750 0 997341 0 994331 0 993109 0 938334 0 949024 0 956532 0 840646 0 007975 0 001042 0 000000 General problems Slide 10 Step 0 Given x1 set k 1 d1 f x0 Step 1 If f xk stop else k argmin f xk dk f xk dk d k Qdk xk 1 xk k dk dk 1 f xk 1 k dk k f xk 1 f xk Step 2 k k 1 goto Step 1 3 3 1 Necessary Optimality Conditions Nonlinear Optimization Slide 11 min f x s t gj x 0 j 1 p hi x 0 i 1 m P x gj x 0 j 1 p hi x 0 i 1 m 3 3 2 The KKT conditions Slide 12 Discovered by Karush Kuhn Tucker in 1950 s Theorem If x is local minimum of P I j gj x 0 set of tight constraints Constraint quali cation condition CQC The vectors gj x j I and hi x i 1 m are linearly independent Slide 13 Then there exist vectors u v p j 1 m 3 uj gj x 0 j 1 p 1 f x uj gj x vi hi x 0 i 1 2 u 0 3 3 Some Intuition from LO Slide 14 Linearize the functions in the neighborhood of the solution x Problem becomes f x f x x x min s t gj x gj x x x 0 j I hi x hi x x x 0 i 1 m Slide 15 This is a LO problem Dual feasibility u j gj x f x u j 0 vi v i to obtain p j 1 3 4 v i hi x f x i 1 j I Change to uj u j m uj gj x m vi hi x 0 uj 0 i 1 Example 1 min Slide 16 f x x1 12 2 x2 6 2 s t h1 x 8x1 4x2 20 0 g1 x x21 x22 3x1 4 5x2 6 5 0 g2 x x1 9 2 x22 64 0 4 x 2 1 g1 x 0 g2 x 14 h1 x 0 Slide 17 I 1 f x 20 14 g1 x 7 2 5 g2 x 14 2 h1 x 8 4 u1 4 u2 0 v1 1 g1 x h1 x linearly independent f x u1 g1 x u2 g2 x v1 h1 x 0 20 7 14 8 0 4 0 1 14 2 5 2 4 0 3 5 Example 2 Slide 18 max x Qx s t x x 1 Q arbitrary Not a convex optimization problem min x Qx s t x x 1 3 5 1 KKT Slide 19 2Qx 2ux 0 x x u 1 0 u 1 x x 0 Slide 20 3 5 2 Solutions of KKT x 0 u 0 Obj 0 x 0 Qx u x x eigenvector of Q with non negative eigenvalue u x Qx u x x u Thus pick the largest nonnegative eigenvalue u of Q The solution is the corresponding eigenvector x normalized such that x x 1 If all eigenvalues are negative x 0 5 3 6 Are CQC Necessary Slide 21 min x1 s t x21 x2 0 x2 0 Feasible space is 0 0 KKT 1 2x1 0 0 u v 0 1 1 0 KKT multipliers do not exist while still 0 0 is local minimum Check g1 0 0 and h1 0 0 3 7 Constrained Quali cation Slide 22 Slater condition There exists an x0 such that gj x0 0 j 1 p and hi x0 0 for all i 1 m Theorem Under the Slater condition the KKT conditions are necessary 4 Su cient Optimality Conditions Slide 23 Theorem If x feasible for P Feasible set is P is convex and f x convex There exist vectors u v u 0 f x p uj gj x m vi hi x 0 i 1 j 1 uj gj x 0 j …