Optimization: Conjugate Gradient & Constraints

1 Outline 1. 2. 3. 4. 5. Slide 1 The Conjugate Gradient Algorithm Necessary Optimality Conditions Sucient Optimality Conditions Convex Optimization Applications 2 The Conjugate Gradient Algorithm 2.1 Quadratic functions min f (x) = 21 x Qx + c x De nition: d1 : : : dn are Q-conjugate if di 6= 0 diQdj = 0 i 6= j Proposition: If d1 : : : dn are Q-conjugate, then d1 : : : pendent. Slide 2 0 0 0 2.2 Motivation d are linearly inden Given Q-conjugate d1 : : : dn , and xk , compute min f (xk + dk ) = c xk + c dk + 1 (xk + d ) Q(xk + d ) = k k 2 f (xk ) + rf (xk ) dk + 21 2 dk Qdk Solution: xk ) dk ^ k = ;rdf (Qd xk+1 = xk + ^kdk 0 Slide 3 0 0 0 0 0 0 k k 2.3 Expanding Subspace Theorem d1 : : : d are Q-conjugate. Then, xk+1 solves min f (x ) k X s:t: x = x1 + j dj n j �1 Moreover, xn+1 = x : � 1 Slide 4 2.4 The Algorithm Slide 5 Step 0 Given x1 , set k := 1, d1 = ;rf (x0 ) Step 1 For k = 1 : : : n do: If jjrf (xk )jj  , stop else: xk ) dk ^ k = argmin f (xk + dk ) = ;rdf (Qd 0 0 k k xk+1 = xk + ^kdk k+1 dk+1 = ;rf (xk+1) + kdk k = ;rfd(xQd) Qdk 0 0 k k 2.5 Correctness Slide 6 Theorem: The directions d1 : : : dn are Q-conjugate. 2.6 Convergence Properties  This is a nite algorithm.  If there are only k distinct eigenvalues of Q, the CGA nds an optimal Slide 7 solution in k steps.  Idea of pre-conditioning. Consider min f (Sx) = 21 (Sx) Q(Sx) + c Sx so that the number of distinct eigenvalues of S QS is small 0 0 0 2.7 Example 0 B B BB Q B B B B B @ = 35 19 22 28 16 3 16 6 4 4 19 43 33 19 5 2 5 4 0 0 f (x) = 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 x Qx ; c x 2 1 0 16 5 6 14 8 1 12 2 2 4 Q) � 17
641 0 6 4 2 6 2 0 2 4 0 0 4 0 2 2 4 1 2 0 2 4 4 0 4 4 8 4 4 0 4 16 Slide 8 1 C CCC CC CC CA and = ( 2 0; B BBB ; c B BB ; BB @ ;;  Q;  ; 1 0 0 3 0 2 0 6 7 4 = Q ( ( ) 1 )+1 2 1 C CCC CC CC CA = 0:999774 Slide 9 f (xk ) f (xk ) ; f (x� ) 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 k 1 2 3 4 5 6 7 8 9 10 11 12 ; ; ; ; ; ; ; ; ; ; 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 2.8 General problems Slide 10 Step 0 Given x1 , set k := 1, d1 = ;rf (x0 ) Step 1 If jjrf (xk )jj  , stop else: xk ) dk ^ k = argmin f (xk + dk ) = ;rdf (Qd 0 0 k k xk+1 = xk + ^kdk dk+1 = ;rf (xk+1) + k dk f (xk+1)jj k = jjr jjrf (xk )jj Step 2 k  k + 1, goto Step 1 3 Necessary Optimality Conditions 3.1 Nonlinear Optimization min f (x) s:t: gj (x)  0 hi (x) = 0 Slide 11 j = 1 ::: p i = 1 ::: m P = fxj gj (x)  0 j = 1 : : : p hi(x) = 0 i = 1 : : : mg 3 3.2 The KKT conditions Discovered by Karush-Kuhn-Tucker in 1950's. Theorem If  x is local minimum of P  I = fj j gj (x) = 0g, set of tight constraints  Constraint quali cation condition (CQC): The vectors rgj (x), j 2 I and rhi(x), i = 1 : : : m are linearly independent Then, there exist vectors (u v): 1. rf (x) + p X j �1 uj rgj (x) + 2. u  0 3. uj gj (x) = 0 m X i�1 Slide 12 Slide 13 vi rhi(x) = 0 j = 1 ::: p 3.3 Some Intuition from LO Linearize the functions in the neighborhood of the solution x. Problem becomes: min f (x ) + rf (x) (x ; x) s:t: gj (x) + rgj (x) (x ; x)  0 j 2 I hi (x) + rhi (x) (x ; x) = 0 i = 1 : : : m Slide 14 0 0 0 Slide 15 This is a LO problem. Dual feasibility: X j 2I u^j rgj (x) + Change to uj = ;u^j rf (x) + m X i�1 v^i rhi (x) = rf (x) u^j  0 vi = ;v^i to obtain: p X j �1 uj rgj (x) + m X i�1 3.4 Example 1 vi rhi(x) = 0 uj  0 min 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 Slide 16 x = (2 1)  g1(x) = 0 g2(x) = ;14 h1(x) = 0: 0 Slide 17       I = f1g rf (x) = (;20 14)  rg1(x) = (7 ;2:5) rg2(x) = (;14 2)  rh1 (x) = (8 4) u1 = 4, u2 = 0, v1 = ;1 rg1(x), rh1(x) linearly independent rf (x) + u1rg1(x) + u2rg2(x) + v1 rh1(x) = 0 0 0 0  ;20  0       0 = 7 ;14 + (;1) 8 14 + 4 ;2:5 + 0 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 0 0 0 0 3.5.1 KKT Slide 19 ;2Qx + 2ux = 0 xx  1 u  0 u(1 ; x x) = 0 0 0 Slide 20 3.5.2 Solutions of KKT  x = 0, u = 0, Obj = 0.  x =6 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 0 0 the corresponding eigenvector x^ normalized such that x^ x^ = 1. If all eigenvalues are negative, x^ = 0. 0 5 3.6 Are CQC Necessary? Slide 21 min x1 s:t: x12 ; x2  0 x2 = 0 Feasible space is (0 0). KKT:  1   2x   0   0  1 0 + u ;1 + v 1 = 0 KKT multipliers do not exist, while still (0 0) is local minimum. Check rg1(0 0) and rh1(0 0). 0 3.7 Constrained Quali cation Slater condition: There exists hi (x0) = 0 for all i = 1 : : : m. an x0 such that gj (x0 ) < 0, j = 1 : : : p, and Slide 22 Theorem Under the Slater condition the KKT conditions are necessary. 4 Sucient 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: rf (x) + p X j �1 uj rgj (x) + uj gj (x) = 0 m X i�1 vi rhi (x) = 0 j = 1 ::: p Then, x is a global minimum of P . 4.1 Proof  Let x 2 P . Then (1 ; )x + x 2 P for  2 0 1].  gj (x + (x ; x))  0 ) rgj (x) (x ; x)  0 0 6 Slide 24  Similarly, hi(x + (x ; x))  0 ) rhi(x) (x ; x) = 0 0  Thus, Slide 25 rf (x) (x ; x) = 1 0p m X X ; @ uj rgj (x) + vi rhi (x)A (x ; x)  0 0 0 i�1 j �1 ) f (x)  f (x): 5 Convex Optimization  The KKT conditions are always necessary under CQC.  The KKT conditions are sucient for convex optimization problems.  The KKT conditions are necessary and sucient for convex optimization Slide 26 problems under CQC.  min f (x ) s.t. Ax = b x  0, f (x) convex, KKT are necessary and sucient even without CQC. 5.0.1 Separating hyperplanes Theorem Let S be a nonempty closed convex subset of c0 f (x) 8 (u0 u v) 2 U: 7 Slide 28 Slide 29 S . x* c  c0  0 and cj  0 for j 2 I (constraint gj (x)  0 tight). Why? If (u0 u v) 2 U , then (u0 +  u v) 2 U for   0. Thus, 8   0 c0 + p X j �1 cj uj + m X i�1 di vi > c0 f (x) ) c0  0:  Select (u0 u v) = (f (x ) +  g1(x) : : : gp (x) h1(x) : : : hm (x)) 2 U  p m c0(f (x ) + ) +  Take  ! 0: c0 f (x) + X j �1 p X j �1 cj gj (x) + cj gj (x) + X i�1 m X i�1 dihi (x) > c0f (x ) dihi (x)  c0 f (x)  c0 > 0 (constrained quali cation needed here).  p m X X f (x) + uj gj (x) + vi hi (x)  f (x) uj  0  j �1 f (x ) + i�1 p X j �1 uj gj (x) + f (x) + p X j �1 m X i�1 vi hi(x)  f (x )  uj gj (x) + 8 m X i�1 vi hi(x):  Thus, 0 1 p m X X f (x ) = min @f (x) + uj gj (x) + vihi (x)A p X j �1 j �1 i�1 uj gj (x) = 0 ) uj gj (x) = 0  Unconstrained optimality conditions: rf (x) + p X j �1 uj rgj (x) + m X i�1 vi rhi (x) = 0 6 Applications 6.1 Linear Optimization Slide 30 min c x s:t: Ax = b 0 x0 min c x s:t: Ax ; b = 0 ;x  0 0 6.1.1 KKT c + A u^ ; v = v  0 0 x  0 0 vj xj = 0 Ax ; b = 0 u = ;u^ Au (cj ; A u)xj Ax ; b x 0 0 j  c dual feasibility = 0 complementarity = 0 primal feasibility  0 primal feasibility 9 Slide 31 6.2 Portfolio Optimization x =weights of the portfolio Slide 32 max r x ;  21 x Qx s:t: e x = 1 0 0 0 min ;r x +  21 x Qx s:t: e x = 1 0 0 0 6.2.1 KKT ;r + Qx + ue = 0 x = 1 Q 1(r ; ue) ; e x = 1 ) e Q 1(r ; ue) =  1 u = e Q r1;  eQ e 0 ; 0 ; 0 0 ; As  changes, tradeo of risk and return changes. The allocation changes as well. This is the essense of modern portfolio theory. 10 Slide 33