Homework 1 Solutions
Wanshun Gao December 4, 2014
1.1.4 We set f (x) = −1/x + x Then we have f (x) = −1/x2 + 1 The stationary points are: −1 Since x>0 the local minima is x=1 So for all x>0 f(x)=-1/x+x>f(1)=2 and
2 2

f (x) = 2/x3

and

1

f (1) > 0

1.3.5 The Goldstein rule means fixing σ ∈ (0, 1/2)and then choosing each αk to satisfy f (xk + αk dk ) − f (xk ) ≤1−σ [GR] σ≤ αk ( f (xk ))T dk Then αk is used in calculating xk+1 := xk + αk dk . With the steepest descent method, dk = − f (xk ). Assume Q = QT , so f (x) = Qx and f (x + y) = f (x) + xT Qy + f (y). Thus f (xk+1 ) = f (xk ) + αk (dk )T Qx + f (αk dk ) = f (xk ) − αk ||dk ||2 + (αk )2 f (dk ) [1]

This allows us to rewrite the middle term of [GR] as follow: σ ≤ −1 + αk f (dk )/||dk ||2 ≤ 1 − σ. That is, σ − 1 ≤ −αk f (dk )/||dk ||2 ≤ −σ; so we can rewrite [GR] as σ||dk ||2 (1 − σ)||dk ||2 ≤ αk ≤ f (dk ) f (dk ) Since σ ≤ 1/2, we have σ(1 − σ) ≥ σ − σ 2 + 2σ − 1 = σ − (1 − σ)2 Since Q = QT obtain [3] [2]

0, we may appl the Kantorovich inequality (to dk ) and

16M m ||dk ||4 [(dk )T dk ]2 = ≥ k )f (xk ) 1 k T k 1 k T −1 k f (d (M + m)2 [(d ) Qd ] [(d ) Q d ] 2 2 Putting the numbered results together,

[4]

we have as we were to prove.