Optimization Methods - Line Searches and Newton's Method

1 Last Lecture Slide 1 Necessary Conditions for Optimality (identi
es candidates) local min ) r ( ) = 0, r2 ( ) PSD x f x f x Su cient Conditions for Optimality rf (x ) = 0 r2 ( ) psd f x x ( )) 2B x Characterizations of Convexity a. convex , ( )  ( ) + r ( )0 ( b. convex , r2 ( ) PSD 8 f f y f f f x f x f x y x loc. min. ; x) 8x y x convex then global min , r ( ) = 0 f x 2 Steepest descent 2.1 The algorithm Step 0 Given x0, set := 0. Step 1 dk := ;r (xk ). If jjdk jj  , then stop. Step 2 Solve min
( ) := (xk + dk) for the Slide 2 k f
h  f  step-length k , perhaps chosen by an exact or inexact line-search. Step 3 Set xk+1  xk + k dk,  + 1. Go to Step 1.   k k 3 Outline 1. 2. 3. 4. 5. Slide 3 Bisection Method - Armijo's Rule Motivation for Newton's method Newton's method Quadratic rate of convergence Modi
cation for global convergence 4 Choices of step sizes ( k + k) k Limited Minimization: +
20s] ( Constant stepsize k = constant M in
f x Slide 4 d M in  f x s 1 k d ) Diminishing stepsize: Armijo Rule P !0 k  k k =1 4.1 Bisection Line- Search Algorithm 4.1.1 Convex functions Slide 5  := arg min ( ) := arg min (x + d )

 h  f  If (x) is convex, ( ) is convex. Find  for which 0 ( ) = 0 0( ) = r ( x + d)0 d f h   h h   f  4.1.2 Algorithm Step 0. Set = 0. Set k L := 0 and U Slide 6 := ^.  + L and compute ( ~). 2 If ( ~) 0, re-set U := ~. Set  + 1. If ( ~) 0, re-set L := ~. Set  + 1. If ( ~) = 0, stop. Step k. Set ~ =  0 h 0 h 0 h U  0 h   >   k k  <   k k  4.1.3 Analysis At the iteration of the bisection algorithm, the current interval  L U ] must contain a point  : 0(  ) = 0 At the th iteration of the bisection algorithm, the length of the current interval  L U ] is
k length = 21 ( ^) kth   h  k    : A value of such that j   j 
; can be found in at most &  ^ !' log2 
steps of the bisection algorithm. 2  Slide 7 4.1.4 Example Slide 8 ( ) = ( 1+ ) ; 0 6( 2 + 2 ) + 4( 3 + 3) + 4 X +0 25( 4 + 4) ; log( i + i ) ; i=1  ! 4 4 X X ; log (5 ; i; i h  x : d1 : x x x  i=1 where ( x1 x2 x3 x4 x d x and d d d i=1 ) = (1 1 1 1)0 and ( d d1 d2 d3 d4 ) = (;1 0 6 ;4 ;0 25)0. : : ( ) = 4 65 ; 17 4225 ; log(1 ; ) ; log(1 + 0 6 ) ; ; log(1 ; 4 ) ; log(1 ; 0 25 ) ; log(1 + 4 65 ) 06 4 1 0( ) = ;17 4225 + 1; ; 1+0 6 + 1;4 + + 1 ;0 02525 ; 1 +4 46565 h  : :    h  : Slide 9 :   :  : :  :   : : :  :  Slide 10 10 0 0.1 0.05 0.15 0.2 0.25 −10 Slide 11 −20 k 1 2 3 4 5 6 7 8 9 10 k l k u 0:0000000 0:0000000 1:0000000 0:5000000 0:1250000 0:1875000 0:2500000 0:2500000 0:0000000 0:1875000 0:1875000 0:1953125 0:1953125 0:1953125 0:2500000 h0 ( ~) NaN NaN ;11:520429338348 ;2:952901763683 13:286386294218 0:2187500 0:2031250 ;0:605144021505 0:1992188 0:1972656 ;0:265032213496 0:2031250 3 2:502969022220 0:831883373151 0:087369215988 Slide 12 k l k 20 0:1970253 0:1970272 0:1970268 0:1970268 0:1970268 30 40 0:1970268 41 0:1970268 0:1970268 42 43 0:1970268 44 0:1970268 45 0:1970268 46 0:1970268 47 k u 0:1970268 0:1970268 0:1970268 0:1970268 0:1970268 0:1970268 0:1970268 0:1970268 h0 ( ~) ;0:000184301091 ;0:000000146531 0:000000000189 0:000000000023 ;0:000000000059 ;0:000000000018 0:000000000003 ;0:000000000008 ;0:000000000002 0:000000000000 4.2 Armijo Rule Bisection is accurate but may be expensive in practice Need cheap method guaranteeing sucient accuracy Inexact line search method. Requires two parameters: 2 (0 1),  ( ) = (0) + 0(0)  acceptable by Armijo's rule if: ( )   ( ) ( )   ( ) (prevents the step size be small) (i.e. ( k +  k )  ( k ) +  r ( k )0 k ) We get a range of acceptable stepsizes. Step 0: Set = 0, 0 =  0 Step k: If ( k )  ( k ), choose k stop. If ( k ) ( k ) let (for example, = 2)
h  h Slide 13  > 1. 
h  h  h  f x h  h  d k h  f x  
f x  > h  Slide 14 d  h  > h  k +1  = 1 k   5 Newton's method 5.1 History Slide 15 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 Slide 16 Consider min (x ) Taylor series expansion around x (x) (x) = (x) + r (x)0 ( ; )+ 1 0 2 2 ( ; ) r ( )( ; ) Instead of min (x), solve min (x), i.e., r (x) = 0 r (x ) + r2 (x)(x ; x) = 0 )x;x  = ;(r2 (x));1r (x) f f g f x f x f f x g f x x x x g f f f The direction d = ;(r2 (x));1 r (x) is the Newton direction f f 6.2 The algorithm Slide 17 Step 0 Given x0, set := 0. Step 1 dk := ;(r2 (xk));1r (xk). k f f If jjdk jj  , then stop. Step 2 Set xk+1  xk + dk,  + 1. Go to Step 1.
k k 6.3 Comments Slide 18 The method assumes that r2 (xk ) is nonsingular at each iteration There is no guaranteee that (x k+1)  (xk ) We can augment the algorithm with a line-search: min (xk + dk )
f f f f  6.4 Properties Theorem If H = r2 (xk ) is PD, then dk is a descent direction: Proof: r (xk )0 dk = ;r (xk )0 H ;1 r (xk ) 0 if H ;1 is PD. But, f f f f 0 v0 (H ;1)0 HH ;1v = v0H ;1 v ) H ;1 is PD < 5 < x )0d rf ( k k < 0 Slide 19 6.5 Example 1 f x x f x x x x f )d Slide 20 ( ) = 7 ; log = 71 = 0 14857143 00 ( ) = 1 0( ) = 7 ; 1 2

;1 7; 1 = ;7 = ;( 00 ( ));1 0 ( ) = ; 12 ;  k +1 = k + k ; 7( k )2 = 2 k ; 7( k )2 : x f x f x x x x x x x x x x 2 x x Slide 21 k k k x x 0 1 1 -5 2 -185 3 -239945 4 -4E11 5 -112E22 6 7 8 0 0 0 0 0 0 0 0 0 k k x 0.01 0.0193 0.03599 0.062917 0.098124 0.128849782 0.141483700 0.142843938 0.142857142 x 0.1 0.13 0.1417 0.14284777 0.142857142 0.142857143 0.142857143 0.142857143 0.142857143 6.6 Example 2 ) = ; log(1 ; 1 ; 2) ; log 1 ; log 2 2 1 3 1 ; 6 1 ; 1 ; 2 1 77 r ( 1 2) = 6 4 1 5 1 ; 1; 1; 2 2
2
2
2 1 1 1 1; 1; 2 + 1 1; 1 ; 2
2
2
2 1 1 1 1; 1; 2 1; 1; 2 + 1 ( f x1 x2 x f x r2 f (x1 2 66 2) = 6 4 x x x x x (
1 1 2) = 3 3 x1 x x x x x x x x x x x x x ( f x1 x2 6 x ) = 3 295836867 : Slide 22 x x x 3 77 75 Slide 23 k k x1 0 1 2 3 4 5 6 7 0.85 0.7170068 0.5129752 0.35247858 0.33844902 0.33333772 0.33333334 0.33333333 x x jj k jj ; x2 0.05 0.09659864 0.17647971 0.27324878 0.32623807 0.33325933 0.33333333 0.33333333 0.58925565 0.45083106 0.23848325 0.06306103 0.00874717 7.4133E-05 1.1953E-08 1.5701E-16 7 Quadratic convergence Recall z Example: zn = = nlim !1 2n a ,0 Slide 24 lim sup jj n+1;;j2 j = z zn n!1 < a < z zn z  < 1 1, = 0 z jzn+1 ; z j jzn ; z j2 = 2n+1 a +1 n a2 =1 7.1 Intuitive statement Theorem Suppose (x) 2 3 (thrice cont. di/ble), x : r ( ) = 0 and r2 (x ) is nonsingular. If Newton's method is started suciently close to x , the sequence of iterates converges quadratically to x . f Slide 25 f x C f Lemma: Suppose (x) 2 Then 8 0, 9 f
> on x y f x f y
H y x y  jjx ; yjj2 7.2 Formal statement Theorem Suppose twice cont. di/ble. Let g(x) = r (x) H (x) = r2 (x), and x : g(x ) = 0. Suppose (x) is twice dierentiable and its Hessian satis
es: jjH (x )jj  jjH (x) ; H (x )jj  jjx ; x jj 8x : jjx ; x jj  (Reminder: If A is a square matrix: j njg) jjAjj = max jjAxjj = maxfj 1j x:jjxjj=1 f f f f h L   7 :::  Slide 27 Suppose
2 jjx ; x jj  min 3 = Let x be the next iterate in the Newton method. Then,
jjx  ; x jj  jjx ; x jj2 32 and h  Slide 28 : L h L x x jj jj  ; < x x jj jj ; < : 7.3 Proof x ; x Slide 29 = x ; H (x);1g(x) ; x
= x ; x + H (x);1 g(x ) ; g(x) = x ; x + H (x);1 Z1 H (x + (x� ; x))(x� ; x) (Lemma 1) 0 Z1 = H (x);1 (H (x + (x� ; x)) ; H (x)) (x� ; x) t dt t 0 x x jj jj  ; dt Slide 30 H (x);1 jj   Z 1  H (x + (x� ; x)) ; H (x)  jjx ; x� jj  jj t 0 dt Z1 H (x);1jj  jjx ; x�jj jjx ; x� jj 0 1 ;1 � = 2 jjH (x) jj  jjx ; x jj2  jj L t dt L Now h H(x )jj H(x) + H (x ) ; H (x)jj H(x)jj + jjH(x ) ; H (x)jj H(x)jj + jjx ; xjj ) jjH (x)jj  ; jjx ; x jj  jj = jj  jj  jj L h H(x) ) jj Slide 31 ;1 jj L 1   jjH (x)jj 8 1 h x x jj ; Ljj ; Slide 32 x x jj ) jj  ; x ; x�jj2 2( jjx ; x� jj2 2(  jj  L h x x jj) ; Ljj ; L h = 32 jjx ; x� jj2 ; 32 h) L h 7.4 Lemma 1 Slide 33 Fix w Let ( ) = g(x + (x� ; x))0 w (0) = g(x)0 w (1) = g(x )0 w 0 ( ) = w0H (x + (x� ; x))(x� ; x) R (1) = (0) + 01 0( ) ) : t t t t t dt Slide 34 w : w0(g(x ) ; g(x)) = Z1 0 w H (x + (x� ; x))(x� ; x) 8 t 0 ) Z g(x ) ; g(x) = 0 1 dt H (x + (x� ; x))(x� ; x) t dt 7.5 Critical comments The iterates from Newton's method are equally attracted to local min and local max. We do not know in general. Note, however, that they are only used in the proof, not in the algorithm. We do not assume convexity, only that (x ) is nonsingular and not badly behaved near x .  h Slide 35 L H Slide 36 7.6 Properties of Convergence Proposition: Let r k = jj k x ; x jj and = 32Lh . If k 0;x x C r k  1( C Cr jj < then ) 0 2k Slide 37 9 Proposition: If jj 0;x x jj >
> 0 ) jjxk ; x jj <
8k 2 log( 1 ) 3 C 6 log( log( Cr1 0 ) 77 6 66 log 2 77 8 Solving systems of equations g(x) = 0 g(x +1) g(x ) + rg(x )(x +1 ; x ) ) x +1 = x ; (rg(x ));1g(x ) Application in optimization: g(x) = r (x) t t t t t t t Slide 38 t t f 9 Modi cations for global convergence Perform line search When Hessian is singular or near singular, use:
;1 k k 2 k d = ; r (x ) + D r (xk) f D is a diagonal matrix: Slide 39 f k x ) + D is PD r2f ( k 10 Summary 1. Line search methods: Bisection Method. Armijo's Rule. 2. The Newton's method 3. Quadratic rate of convergence 4. Modi
cation for global convergence 10 k Slide 40