Lecture 19: Line Searches and Newton’s Method

15.093 Optimization Methods Lecture 19: Line Searches and Newton’s Method 1 Last Lecture • Necessary Conditions for Optimality (identifies candidates) x∗ local min ⇒ ∇f (x∗ ) = 0, ∇2 f (x∗ ) PSD • Sufficient Conditions for Optimality ∇f (x∗ ) = 0 ∇2 f (x) psd x ∈ Bǫ (x∗ ) ⇒ x∗ loc. min. • Characterizations of Convexity a. f convex ⇔ f (y) ≥ f (x) + ∇f (x)′ (y − x) ∀x, y b. f convex ⇔ ∇2 f (x) PSD ∀x • f convex then global min ⇔ ∇f (x∗ ) = 0 2 Steepest descent 2.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. 3 Outline 1. Bisection Method - Armijo’s Rule 2. Motivation for Newton’s method 3. Newton’s method 4. Quadratic rate of convergence 5. Modification for global convergence 4 Choices of step sizes • M inλ f (xk + λdk ) • Limited Minimization: M inλ∈[0,s] f (xk + λdk ) • Constant stepsize λk = s constant 1 • Diminishing stepsize: λk → 0, • Armijo Rule 4.1 4.1.1 P k λk = ∞ Bisection Line- Search Algorithm Convex functions λ̄ := arg min h(λ) := arg min f (x̄ + λd̄) λ λ If f (x) is convex, h(λ) is convex. Find λ̄ for which h′ (λ) = 0 h′ (λ) = ∇f (x̄ + λd̄)′ d̄ 4.1.2 Algorithm Step 0. Set k = 0. Set λL := 0 and λU := λ̂. Step k. λU + λL ′ and compute h (λ̃). 2 ′ If h (λ̃) > 0, re-set λU := λ̃. Set k ← k + 1. Set λ̃ = ′ If h (λ̃) < 0, re-set λL := λ̃. Set k ← k + 1. ′ If h (λ̃) = 0, stop. 4.1.3 Analysis • At the kth iteration of the bisection algorithm, the current interval [λL , λU ] must contain a point λ̄: h′ (λ̄) = 0 • At the k th iteration of the bisection algorithm, the length of the current interval [λL , λU ] is  k 1 (λ̂). length = 2 • A value of λ such that |λ − λ̄| ≤ ǫ can be found in at most & !' λ̂ log2 ǫ steps of the bisection algorithm. 2 4.1.4 Example = (x1 + λd1 ) − 0.6(x2 + λd2 ) + 4(x3 + λd3 ) + 4 X log(xi + λdi ) − +0.25(x4 + λd4 ) − h(λ) i=1 − log (5 − 4 X xi − λ 4 X i=1 i=1 di ! where (x1 , x2 , x3 , x4 ) = (1, 1, 1, 1)′ and (d1 , d2 , d3 , d4 ) = (−1, 0.6, −4, −0.25)′. h(λ) = and h′ (λ) 4.65 − 17.4225λ − log(1 − λ) − log(1 + 0.6λ) − − log(1 − 4λ) − log(1 − 0.25λ) − log(1 + 4.65λ) 1 0.6 4 − + + 1 − λ 1 + 0.6λ 1 − 4λ 4.65 0.25 − + 1 − 0.25λ 1 + 4.65λ = −17.4225 + 10 0 0.05 0.1 0.15 0.2 −10 −20 k 1 2 3 4 5 6 7 8 9 10 λkl 0.0000000 0.0000000 0.0000000 0.1250000 0.1875000 0.1875000 0.1875000 0.1953125 0.1953125 0.1953125 λku 1.0000000 0.5000000 0.2500000 0.2500000 0.2500000 0.2187500 0.2031250 0.2031250 0.1992188 0.1972656 3 h′ (λ̃) NaN NaN −11.520429338348 −2.952901763683 13.286386294218 2.502969022220 −0.605144021505 0.831883373151 0.087369215988 −0.265032213496 0.25 k 20 30 40 41 42 43 44 45 46 47 4.2 λkl 0.1970253 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 λku 0.1970272 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 0.1970268 h′ (λ̃) −0.000184301091 −0.000000146531 0.000000000189 0.000000000023 −0.000000000059 −0.000000000018 0.000000000003 −0.000000000008 −0.000000000002 0.000000000000 Armijo Rule Bisection is accurate but may be expensive in practice Need cheap method guaranteeing sufficient accuracy Inexact line search method. Requires two parameters: ǫ ∈ (0, 1), σ > 1. h̄(λ) = h(0) + λǫh′ (0) λ̄ acceptable by Armijo’s rule if: • h(λ̄) ≤ h̄(λ̄) • h(σλ̄) ≥ h̄(σλ̄) (prevents the step size be small) ¯ k ) ≤ f (xk ) + λǫ ¯ ∇f (xk )′ dk ) (i.e. f (xk + λd We get a range of acceptable stepsizes. Step 0: Set k = 0, λ0 = λ̄ > 0 Step k: If h(λk ) ≤ h̄(λk ), choose λk stop. If h(λk ) > h̄(λk ) let λk+1 = (for example, σ = 2) 5 5.1 1 k σλ Newton’s method History Steepest Descent is simple but slow Newton’s method complex but fast Origins not clear Raphson became member of the Royal Society in 1691 for his book “Analysis Aequationum Universalis” with Newton method. Raphson published it 50 years before Newton. 4 6 Newton’s method 6.1 Motivation Consider min f (x) • Taylor series expansion around x̄ f (x) ≈ g(x) = f (x̄) + ∇f (x̄)′ (x − x̄)+ 1 (x − x̄)′ ∇2 f (x̄)(x − x̄) 2 • Instead of min f (x), solve min g(x), i.e., ∇g(x) = 0 ∇f (x̄) + ∇2 f (x̄)(x − x̄) = 0 • ⇒ x − x̄ = −(∇2 f (x̄))−1 ∇f (x̄) • The direction d = −(∇2 f (x̄))−1 ∇f (x̄) is the Newton direction 6.2 The algorithm Step 0 Given x0 , set k := 0. Step 1 dk := −(∇2 f (xk ))−1 ∇f (xk ). If ||dk || ≤ ǫ, then stop. Step 2 Set xk+1 ← xk + dk , k ← k + 1. Go to Step 1. 6.3 Comments • The method assumes that ∇2 f (xk ) is nonsingular at each iteration • There is no guaranteee that f (xk+1 ) ≤ f (xk ) • We can augment the algorithm with a line-search: min f (xk + λdk ) λ 6.4 Properties Theorem If H = ∇2 f (xk ) is PD, then dk is a descent direction: ∇f (xk )′ dk < 0 Proof: ∇f (xk )′ dk = −∇f (xk )′ H −1 ∇f (xk ) < 0 if H −1 is PD. But, 0 < v ′ (H −1 )′ HH −1 v = v ′ H −1 v ⇒ H −1 is PD 5 6.5 Example 1 1 = 0.14857143 7 1 1 f ′ (x) = 7 − , f ′′ (x) = 2 x x   −1  1 1 7 − = x − 7x2 ⇒ d = −(f ′′ (x))−1 f ′ (x) = − x2 x x∗ = f (x) = 7x − log x,
xk+1 = xk + xk − 7(xk )2 = 2xk − 7(xk )2 k 0 1 2 3 4 5 6 7 8 6.6 xk 1 -5 -185 -239945 -4E11 -112E22 xk 0 0 0 0 0 0 0 0 0 xk 0.01 0.0193 0.03599 0.062917 0.098124 0.128849782 0.141483700 0.142843938 0.142857142 xk 0.1 0.13 0.1417 0.14284777 0.142857142 0.142857143 0.142857143 0.142857143 0.142857143 Example 2 f (x1 , x2 ) = − log(1 − x1 − x2 ) − log x1 − log x2   1 1 −  1 − x1 − x2 x1   ∇f (x1 , x2 ) =   1 1  − 1 − x1 − x2 x2   2  2  2 1 1 1 +  1−x −x x1 1 − x1 − x2 1 2  ∇2 f (x1 , x2 ) =   2  2  2  1 1 1 + 1 − x1 − x2 1 − x1 − x2 x1 (x∗1 , x∗2 ) =  1 1 , 3 3  , f (x∗1 , x∗2 ) = 3.295836867 6      k 0 1 2 3 4 5 6 7 7 xk1 0.85 0.7170068 0.5129752 0.35247858 0.33844902 0.33333772 0.33333334 0.33333333 xk2 0.05 0.09659864 0.17647971 0.27324878 0.32623807 0.33325933 0.33333333 0.33333333 ||x − x∗ || 0.58925565 0.45083106 0.23848325 0.06306103 0.00874717 7.4133E-05 1.1953E-08 1.5701E-16 Quadratic convergence • Recall z = lim zn , n→∞ lim sup n→∞ |zn+1 − z| =δ<∞ |zn − z|2 n • Example: zn = a2 , 0 < a < 1, z = 0 n+1 a2 |zn+1 − z| = =1 |zn − z|2 a2n+1 7.1 Intuitive statement Theorem Suppose f (x) ∈ C 3 (thrice cont. diff/ble), x∗ : ∇f (x∗ ) = 0 and ∇2 f (x∗ ) is nonsingular. If Newton’s method is started sufficiently close to x∗ , the sequence of iterates converges quadratically to x∗ . Lemma: Suppose f (x) ∈ C 3 on ℜn and x a given pt. Then ∀ǫ > 0, ∃β > 0: ||x − y|| ≤ ǫ ⇒ ||∇f (x) − ∇f (y) − H(y)(x − y)|| ≤ β||x − y||2 7.2 Formal statement Theorem Suppose f twice cont. diff/ble. Let g(x) = ∇f (x), H(x) = ∇2 f (x), and x∗ : g(x∗ ) = 0. Suppose f (x) is twice differentiable and its Hessian satisfies: • ||H(x∗ )|| ≥ h • ||H(x) − H(x∗ )|| ≤ L||x − x∗ ||, ∀x : ||x − x∗ || ≤ β (Reminder: If A is a square matrix: ||A|| = max ||Ax|| = max{|λ1 |, . . . , |λn |}) x:||x||=1 7 Suppose   2h ||x − x || ≤ min β, = γ. 3L ∗ Let x ¯ be the next iterate in the Newton method. Then,   2h and ||x ¯ − x∗ || ≤ ||x − x∗ ||2 3L ||x ¯ − x∗ || < ||x − x∗ || < γ. 7.3 Proof x ¯ − x∗ = x − H(x)−1 g(x) − x∗   = x − x∗ + H(x)−1 g(x∗ ) − g(x) = x − x∗ + H(x)−1 Z 1 H(x + t(x∗ − x))(x∗ − x)dt (Lemma 1) 0 Z 1 = H(x)−1 (H(x + t(x∗ − x)) − H(x)) (x∗ − x)dt 0 ||x ¯ − x∗ || ≤ ≤ ||H(x)−1 || Z 1 H(x + t(x∗ − x)) − H(x) · ||x − x∗ ||dt 0 Z 1 ||H(x)−1 || · ||x − x∗ || L||x − x∗ || t dt 0 = Now 1 L||H(x)−1 || · ||x − x∗ ||2 2 h ≤ = ||H(x∗ )|| ||H(x) + H(x∗ ) − H(x)|| ≤ ≤ ||H(x)|| + ||H(x∗ ) − H(x)|| ||H(x)|| + L||x∗ − x|| ⇒ ||H(x)|| ≥ h − L||x − x∗ || ⇒ ||H(x)−1 || ≤ 1 1 ≤ ||H (x)|| h − L||x − x∗ || 8 L 2(h − L||x − x∗ ||) L ≤ ||x − x∗ ||2 2(h − 23 h) 3L = ||x − x∗ ||2 2h ⇒ ||x̄ − x∗ || ≤ ||x − x∗ ||2 7.4 Lemma 1 • Fix w. Let φ(t) = g(x + t(x∗ − x))′ w • φ(0) = g(x)′ w, φ(1) = g(x∗ )′ w • φ′ (t) = w ′ H(x + t(x∗ − x))(x∗ − x) R1 • φ(1) = φ(0) + 0 φ′ (t)dt ⇒ ∀w : w′ (g(x∗ ) − g(x)) = w′ Z 1 H(x + t(x∗ − x))(x∗ − x)dt 0 ⇒ g(x∗ ) − g(x) = Z 1 H(x + t(x∗ − x))(x∗ − x)dt 0 7.5 Critical comments • The iterates from Newton’s method are equally attracted to local min and local max. • We do not know β, h, L in general. • Note, however, that they are only used in the proof, not in the algorithm. • We do not assume convexity, only that H(x∗ ) is nonsingular and not badly behaved near x∗ . 7.6 Properties of Convergence Proposition: Let rk = ||xk − x∗ || and C = 3L 2h . If kx0 − x∗ || < γ then rk ≤ k 1 (Cr0 )2 C 9 Proposition: If ||x0 − x∗ || > ǫ > 0 ⇒ ||xk − x∗ || < ǫ   log( 1 ) log( log( Cǫ1 )   Cr0 ∀k ≥     log 2   8 Solving systems of equations g(x) = 0 g(xt+1 ) ≈ g(xt ) + ∇g(xt )(xt+1 − xt ) ⇒ xt+1 = xt − (∇g(xt ))−1 g(xt ) Application in optimization: g(x) = ∇f (x) 9 Modifications for global convergence • Perform line search • When Hessian is singular or near singular, use:  −1 k 2 k d = − ∇ f (x ) + D ∇f (xk ) k • D k is a diagonal matrix: ∇2 f (xk ) + Dk is PD 10 Summary 1. Line search methods: Bisection Method. Armijo’s Rule. 2. The Newton’s method 3. Quadratic rate of convergence 4. Modification for global convergence 10