Lecture 18: Optimality Conditions and Gradient Methods for Unconstrained Optimization

15.093 Optimization Methods Lecture 18: Optimality Conditions and Gradient Methods for Unconstrained Optimization 1 Outline 1. Necessary and sufficient optimality conditions 2. Gradient methods 3. The steepest descent algorithm 4. Rate of convergence 5. Line search algorithms 2 Optimality Conditions Necessary Conds for Local Optima “If x̄ is local optimum then x̄ must satisfy ...” Identifies all candidates for local optima. Sufficient Conds for Local Optima “If x̄ satisfies ...,then x̄ must be a local optimum ” 3 Optimality Conditions 3.1 Necessary conditions Consider min f (x) x∈ℜn Zero first order variation along all directions Theorem Let f (x) be continuously differentiable. If x∗ ∈ ℜn is a local minimum of f (x), then ∇f (x∗ ) = 0 and ∇2 f (x∗ ) PSD 3.2 Proof Zero slope at local min x∗ • f (x∗ ) ≤ f (x∗ + λd) for all d ∈ ℜn , λ ∈ ℜ 1 • Pick λ > 0 0≤ f (x∗ + λd) − f (x∗ ) λ • Take limits as λ → 0 0 ≤ ∇f (x∗ )′ d, ∀d ∈ ℜn • Since d arbitrary, replace with −d ⇒ ∇f (x∗ ) = 0. Nonnegative curvature at a local min x∗ • f (x∗ + λd) − f (x∗ ) = ∇f (x∗ )′ (λd) + 21 (λd)′ ∇2 f (x∗ )(λd) + ||λd||2 R(x∗ ; λd) where R(x∗ ; y) → 0 as y → 0. Since ∇f (x∗ ) = 0, 1 2 ′ 2 λ d ∇ f (x∗ )d + λ2 ||d||2 R(x∗ ; λd) ⇒ 2 1 f (x∗ + λd) − f (x∗ ) = d′ ∇2 f (x∗ )d + ||d||2 R(x∗ ; λd) λ2 2 ¯ < f (x̄), ∀λ If ∇2 f (x∗ ) is not PSD, ∃d¯: d¯ ′ ∇2 f (x∗ )d¯ < 0 ⇒ f (x∗ + λd) suff. small QED. = 3.3 Example f (x) = 12 x21 + x1 .x2 + 2x22 − 4x1 − 4x2 − x32 ∇f (x) = (x�1 + x2 − 4, x1 + � 4x2 − 4 − 3x22 ) Candidates x∗ = (4, 0) and x̄ = (3, 1) 1 1 ∇2 f (x) = 1 4 − � �6x2 1 1 ∇2 f (x∗ ) = 1 4 PSD x̄ = (3, 1) � � 1 1 ∇2 f (x̄) = 1 −2 Indefinite matrix x∗ is the only candidate for local min 3.4 Sufficient conditions Theorem f twice continuously differentiable. If ∇f (x∗ ) = 0 and ∇2 f (x) PSD in B(x∗ , ǫ), then x∗ is a local minimum. Proof: Taylor series expansion: For all x ∈ B(x∗ , ǫ) f (x) = f (x∗ ) + ∇f (x∗ )′ (x − x∗ ) 1 + (x − x∗ )′ ∇2 f (x∗ + λ(x − x∗ ))(x − x∗ ) 2 for some λ ∈ [0, 1] ⇒ f (x) ≥ f (x∗ ) 2 3.5 Example Continued... At x∗ = (4,�0), ∇f (x∗ ) = 0 �and 1 1 ∇2 f (x) = 1 4 − 6x2 is PSD for x ∈ B(x∗ , ǫ) 2 2 ∗ f (x) = x31 + � x2 and ∇f�(x) = (3x1 , 2x2 ) x = (0, 0) 6x1 0 ∇2 f (x) = is not PSD in B(0, ǫ) 0 2 f (−ǫ, 0) = −ǫ3 < 0 = f (x∗ ) 3.6 Characterization of convex functions Theorem Let f (x) be continuously differentiable. Then f (x) is convex if and only if ∇f (x)′ (x − x) ≤ f (x) − f (x) 3.7 Proof By convexity f (λx + (1 − λ)x) ≤ λf (x) + (1 − λ)f (x) f (x + λ(x − x)) − f (x) ≤ f (x) − f (x) λ As λ → 0, ∇f (x)′ (x − x) ≤ f (x) − f (x) 3.8 Convex functions Theorem Let f (x) be a continuously differentiable convex function. Then x∗ is a minimum of f if and only if ∇f (x∗ ) = 0 Proof: If f convex and ∇f (x∗ ) = 0 f (x) − f (x∗ ) ≥ ∇f (x∗ )′ (x − x∗ ) = 0 3 3.9 Descent Directions Interesting Observation f diff/ble at x̄ ∃d: ∇f (x̄)′ d < 0 ⇒ ∀λ > 0, suff. small, f (x̄ + λd) < f (x̄) (d: descent direction) 3.10 Proof f (x̄ + λd) = f (x̄) + λ∇f (x̄)t d + λ||d||R(x̄, λd) where R(x̄, λd) −→λ→0 0 f (x̄ + λd) − f (x̄) = ∇f (x̄)t d + ||d||R(x̄, λd) λ ∇f (x̄)t d < 0, R(x̄, λd) −→λ→0 0 ⇒ ∀λ > 0 suff. small f (x̄ + λd) < f (x̄). QED 4 Algorithms for unconstrained optimization 4.1 Gradient Methods-Motivation • Decrease f (x) until ∇f (x∗ ) = 0 • f (x̄ + λd) ≈ f (x̄) + λ∇f (x̄)′ d • If ∇f (x̄)′ d < 0, then for small λ > 0, f (x̄ + λd) < f (x̄) 5 Gradient Methods 5.1 A generic algorithm • xk+1 = xk + λk dk • If ∇f (xk ) 6= 0, direction dk satisfies: ∇f (xk )′ dk < 0 • Step-length λk > 0 • Principal example: xk+1 = xk − λk Dk ∇f (xk ) D k positive definite symmetric matrix 4 5.2 Principal directions • Steepest descent: xk+1 = xk − λk ∇f (xk ) • Newton’s method: xk+1 = xk − λk (∇2 f (xk ))−1 ∇f (xk ) 5.3 Other directions • Diagonally scaled steepest descent D k = Diagonal approximation to (∇2 f (xk ))−1 • Modified Newton’s method D k = Diagonal approximation to (∇2 f (x0 ))−1 • Gauss-Newton method for least squares problems f (x) = ||g(x)||2 (∇g(xk )∇g(xk )′ )−1 6 Steepest descent 6.1 The algorithm Step 0 Given x0 , set k := 0. Step 1 dk := −∇f (xk ). If ||dk || ≤ ǫ, then stop. Step 2 Solve minλ h(λ) := f (xk + λdk ) for the step-length λk , perhaps chosen by an exact or inexact line-search. Step 3 Set xk+1 ← xk + λk dk , k ← k + 1. Go to Step 1. 6.2 An example minimize f (x1 , x2 ) = 5x21 + x22 + 4x1 x2 − 14x1 − 6x2 + 20 x∗ = (x∗1 , x∗2 )′ = (1, 1)′ f (x∗ ) = 10 Given x k dk = −∇f (xk1 , xk2 ) = h(λ) = = � −10xk1 − 4xk2 + 14 −2xk2 − 4xk1 + 6 � = � dk1 dk2 � f (xk + λdk ) 5(xk1 + λdk1 )2 + (xk2 + λdk2 )2 + 4(xk1 + λdk1 )(xk2 + λdk2 )− −14(xk1 + λdk1 ) − 6(xk2 + λdk2 ) + 20 5 Dk = (dk1 )2 + (dk2 )2 + (dk2 )2 + 4dk1 dk2 ) Start at x = (0, 10)′ ε = 10−6 λk = 2(5(dk1 )2 x1k 0.000000 −2.252782 0.755548 0.204852 0.940243 0.805625 0.985392 0.952485 0.996429 0.988385 k 1 2 3 4 5 6 7 8 9 10 k 11 12 13 14 15 16 17 18 19 20 21 22 23 24 x2k 10.000000 8.786963 3.200064 2.903535 1.537809 1.465322 1.131468 1.113749 1.032138 1.027806 xk 1 0.999127 0.997161 0.999787 0.999306 0.999948 0.999830 0.999987 0.999959 0.999997 0.999990 0.999999 0.999998 1.000000 0.999999 xk 2 1.007856 1.006797 1.001920 1.001662 1.000469 1.000406 1.000115 1.000099 1.000028 1.000024 1.000007 1.000006 1.000002 1.000001 d1k −26.000000 1.379968 −6.355739 0.337335 −1.553670 0.082462 −0.379797 0.020158 −0.092842 0.004928 dk 1 −0.022695 0.001205 −0.005548 0.000294 −0.001356 0.000072 −0.000332 0.000018 −0.000081 0.000004 −0.000020 0.000001 −0.000005 0.000000 d2k −14.000000 −2.562798 −3.422321 −0.626480 −0.836592 −0.153144 −0.204506 −0.037436 −0.049992 −0.009151 dk 2 −0.012221 −0.002237 −0.002987 −0.000547 −0.000730 −0.000134 −0.000179 −0.000033 −0.000044 −0.000008 −0.000011 −0.000002 −0.000003 −0.000000 ||dk ||2 29.52964612 2.91071234 7.21856659 0.71152803 1.76458951 0.17393410 0.43135657 0.04251845 0.10544577 0.01039370 ||dk ||2 0.02577638 0.00254076 0.00630107 0.00062109 0.00154031 0.00015183 0.00037653 0.00003711 0.00009204 0.00000907 0.00002250 0.00000222 0.00000550 0.00000054 λk 0.0866 2.1800 0.0866 2.1800 0.0866 2.1800 0.0866 2.1800 0.0866 2.1800 λk 0.0866 2.1800 0.0866 2.1800 0.0866 2.1800 0.0866 2.1800 0.0866 2.1803 0.0866 2.1817 0.0866 0.0000 5 x2+4 y2+3 x y+7 x+20 1200 1000 800 600 400 200 0 10 5 0 −5 −10 y 0 −5 −10 x 6 5 10 f (xk ) 60.000000 22.222576 12.987827 10.730379 10.178542 10.043645 10.010669 10.002608 10.000638 10.000156 f (xk ) 10.000038 10.000009 10.000002 10.000001 10.000000 10.000000 10.000000 10.000000 10.000000 10.000000 10.000000 10.000000 10.000000 10.000000 10 8 6 4 2 0 −2 −5 6.3 0 5 Important Properties • f (xk+1 ) < f (xk ) < · · · < f (x0 ) (because dk are descent directions) • Under reasonable assumptions of f (x), the sequence x0 , x1 , . . . , will have at least one cluster point x̄ • Every cluster point x̄ will satisfy ∇f (x̄) = 0 • Implication: If f (x) is a convex function, x̄ will be an optimal solution 7 Global Convergence Result Theorem: f : Rn → R is continuously diff/ble on F = {x ∈ Rn : f (x) ≤ f (x0 )} closed, bounded set Every cluster point x̄ of {xk } satisfies ∇f (x̄) = 0. 7.1 Work Per Iteration Two computation tasks at each iteration of steepest descent: • Compute ∇f (xk ) (for quadratic objective functions, it takes O(n2 ) steps) to determine dk = −∇f (xk ) 7 • Perform line-search of h(λ) = f (xk + λdk ) to determine λk = arg minλ h(λ) = arg minλ f (xk + λdk ) 8 Rate of convergence of algorithms Let z1 , . . . , zn , . . . → z be a convergent sequence. We say that the order of convergence of this sequence is p∗ if � � |zk+1 − z| p∗ = sup p : lim sup < ∞ p k→∞ |zk − z| Let |zk+1 − z| p∗ k→∞ |zk − z| β = lim sup The larger p∗ , the faster the convergence 8.1 Types of convergence ∗ 1. p = 1, 0 < β < 1, then linear (or geometric) rate of convergence 2. p∗ = 1, β = 0, super-linear convergence 3. p∗ = 1, β = 1, sub-linear convergence 4. p∗ = 2, quadratic convergence 8.2 Examples • zk = ak , 0 < a < 1 converges linearly to zero, β = a k • zk = a2 , 0 < a < 1 converges quadratically to zero • zk = 1 k • zk = � �k 8.3 converges sub-linearly to zero 1 k converges super-linearly to zero Steepest descent • zk = f (xk ), z = f (x∗ ), where x∗ = arg min f (x) 8 • Then an algorithm exhibits linear convergence if there is a constant δ < 1 such that f (xk+1 ) − f (x∗ ) ≤δ, f (xk ) − f (x∗ ) for all k sufficiently large, where x∗ is an optimal solution. 8.3.1 Discussion f (xk+1 ) − f (x∗ ) ≤δ<1 f (xk ) − f (x∗ ) • If δ = 0.1, every iteration adds another digit of accuracy to the optimal objective value. • If δ = 0.9, every 22 iterations add another digit of accuracy to the optimal objective value, because (0.9)22 ≈ 0.1. 9 Rate of convergence of steepest descent 9.1 9.1.1 Quadratic Case Theorem Suppose f (x) = 12 x′ Qx − c′ x Q is psd λmax = largest eigenvalue of Q λmin = smallest eigenvalues of Q Linear Convergence Theorem: If f (x) is a quadratic function and Q is psd, then � � 2 λmax k+1 ∗ f (x ) − f (x )  λmin − 1  � ≤ � λmax f (xk ) − f (x∗ ) +1 λmin 9.1.2 Discussion � � 2 λmax f (xk+1 ) − f (x∗ )  λmin − 1  � ≤ � λmax f (xk ) − f (x∗ ) +1 λmin • κ(Q) := λmax λmin is the condition number of Q 9 • κ(Q) ≥ 1 • κ(Q) plays an extremely important role in analyzing computation involv­ ing Q f (xk+1 ) − f (x∗ ) ≤ f (xk ) − f (x∗ ) κ(Q) = λmax λmin � κ(Q) − 1 κ(Q) + 1 �2 Upper Bound on Convergence Constant δ Number of Iterations to Reduce the Optimality Gap by 0.10 0.0023 0.25 0.67 0.96 0.98 0.99 1 2 6 58 116 231 1.1 3.0 10.0 100.0 200.0 400.0 For κ(Q) ∼ O(1) converges fast. For large κ(Q) � �2 κ(Q) − 1 1 2 2 ∼ (1 − ) ∼1− κ(Q) + 1 κ(Q) κ(Q) Therefore (f (xk ) − f (x∗ )) ≤ (1 − 2 k ) (f (x0 ) − f (x∗ )) κ(Q) In k ∼ 12 κ(Q)(−lnǫ) iterations, finds xk : (f (xk ) − f (x∗ )) ≤ ǫ(f (x0 ) − f (x∗ )) 9.2 Example 2 1 f (x) = x′ Qx − c′ x + 10 2 � � � � 20 5 14 Q= c= 5 1 6 κ(Q) = 30.234 � �2 κ(Q)−1 δ = κ(Q)+1 = 0.8760 k xk 1 xk 2 ||dk ||2 1 2 3 4 5 6 7 8 9 10 40.000000 25.542693 26.277558 16.763512 17.247111 10.986120 11.304366 7.184142 7.393573 4.682141 −100.000000 −99.696700 −64.668130 −64.468535 −41.416980 −41.285630 −26.115894 −26.029455 −16.046575 −15.989692 286.06293014 77.69702948 188.25191488 51.13075844 123.88457127 33.64806192 81.52579489 22.14307211 53.65038732 14.57188362 10 λk 0.0506 0.4509 0.0506 0.4509 0.0506 0.4509 0.0506 0.4509 0.0506 0.4509 f (xk ) 6050.000000 3981.695128 2620.587793 1724.872077 1135.420663 747.515255 492.242977 324.253734 213.703595 140.952906 f (xk ) − f (x∗ ) f (xk−1 ) − f (x∗ ) 0.658079 0.658079 0.658079 0.658079 0.658079 0.658079 0.658079 0.658079 0.658079 9.3 k xk 1 xk 2 ||dk ||2 20 30 40 50 60 70 80 90 0.460997 −0.059980 −0.124280 −0.132216 −0.133195 −0.133316 −0.133331 −0.133333 0.948466 3.038991 3.297005 3.328850 3.332780 3.333265 3.333325 3.333332 1.79847660 0.22196980 0.02739574 0.00338121 0.00041731 0.00005151 0.00000636 0.00000078 λk 0.4509 0.4509 0.4509 0.4509 0.4509 0.4509 0.4509 0.0000 f (xk ) 3.066216 0.965823 0.933828 0.933341 0.933333 0.933333 0.933333 0.933333 f (xk ) − f (x∗ ) f (xk−1 ) − f (x∗ ) 0.658079 0.658079 0.658079 0.658079 0.658078 0.658025 0.654656 0.000000 Example 3 1 f (x) = x′ Qx − c′ x + 10 2 � � � � 20 5 14 Q= c= 5 16 6 κ(Q) = 1.8541 � �2 κ(Q) − 1 δ= = 0.0896 κ(Q) + 1 k xk 1 x2k ||dk ||2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 40.000000 19.867118 2.513241 1.563658 0.745149 0.700361 0.661755 0.659643 0.657822 0.657722 0.657636 0.657632 0.657628 0.657627 0.657627 −100.000000 −1.025060 −4.555081 0.113150 −0.053347 0.166834 0.158981 0.169366 0.168996 0.169486 0.169468 0.169491 0.169490 0.169492 0.169491 1434.79336491 385.96252652 67.67315150 18.20422450 3.19185713 0.85861649 0.15054644 0.04049732 0.00710064 0.00191009 0.00033491 0.00009009 0.00001580 0.00000425 0.00000075 11 λk 0.0704 0.0459 0.0704 0.0459 0.0704 0.0459 0.0704 0.0459 0.0704 0.0459 0.0704 0.0459 0.0704 0.0459 0.0000 f (xk ) 76050.000000 3591.615327 174.058930 12.867208 5.264475 4.905886 4.888973 4.888175 4.888137 4.888136 4.888136 4.888136 4.888136 4.888136 4.888136 f (xk ) − f (x∗ ) f (xk−1 ) − f (x∗ ) 0.047166 0.047166 0.047166 0.047166 0.047166 0.047166 0.047166 0.047166 0.047166 0.047166 0.047161 0.047068 0.045002 0.000000 9.4 Empirical behavior • The convergence constant bound is not just theoretical. It is typically experienced in practice. • Analysis is due to Leonid Kantorovich, who won the Nobel Memorial Prize in Economic Science in 1975 for his contributions to optimization and economic planning. • What about non-quadratic functions? – Suppose x∗ = arg minx f (x) – ∇2 f (x∗ ) is the Hessian of f (x) at x = x∗ – Rate of convergence will depend on κ(∇2 f (x∗ )) 10 Summary 1. Optimality Conditions 2. The steepest descent algorithm - Convergence 3. Rate of convergence of Steepest Descent 12