Numerical Methods and Optimization

332 Numerical Methods and Optimization: An Introduction

in our analysis. It is easy to check that q(x)=f(x)+

1

2

x

∗

T

Qx

∗

,sothetwo

functions differ only by a constant. We denote by ∇

k

the gradient of q(x)at

point x

(k)

:

∇

k

= ∇q(x

(k)

)=Q(x

(k)

− x

∗

). (13.14)

The steepest descent iteration for this function is

x

(k+1)

= x

(k)

− α

k

∇

k

, (13.15)

where

α

k

=

∇

T

k

∇

k

∇

T

k

Q∇

k

. (13.16)

Next, we prove that

q(x

(k+1)

) ≤ q(x

(k)

)



1 −

λ

min

(Q)

λ

max

(Q)



,

where λ

min

(Q)andλ

max

(Q) are the smallest and the largest eigenvalues of

Q, respectively. To show this, we first observe that

(x

(k)

− x

∗

)

T

Q(x

(k)

− x

∗

)=(x

(k)

− x

∗

)

T

Q

T

Q

−1

Q(x

(k)

− x

∗

)

=(Q(x

(k)

− x

∗

))

T

Q

−1

(Q(x

(k)

− x

∗

))

= ∇

T

k

Q

−1

∇

k

,

and then express q(x

(k+1)

)int ...