\nabla f (x) = A x - b = A (x - x^{*})

f (x) - f (x^{*}) = \frac{1}{2} (x - x^{*})^{T} A (x - x^{*}) > 0

for

x \neq = x^{*}

, so

x^{*}

is the unique global minimizer. Since

x - x^{*} = A^{- 1} \nabla f (x)

f (x) - f (x^{*}) = \frac{1}{2} \nabla f (x)^{T} A^{- 1} \nabla f (x) .

ii

Solution

Since

\nabla f (x_{k}) = - r_{k}

, exact line search minimizes

f (x_{k} + t r_{k})

0 = r_{k}^{T} (A x_{k} - b) + t, r_{k}^{T} A r_{k} = - r_{k}^{T} r_{k} + t, r_{k}^{T} A r_{k},

t_{k} = \frac{r _{k}^{T} r _{k}}{r _{k}^{T} A r _{k}} .

f (x_{k + 1}) - f (x_{k}) = - \frac{1}{2} \frac{( r _{k}^{T} r _{k} ) ^{2}}{r _{k}^{T} A r _{k}} .

Using

f (x_{k}) - f (x^{*}) = \frac{1}{2} r_{k}^{T} A^{- 1} r_{k}

produces the stated ratio formula. If

l

and

L

are the extreme eigenvalues,

r_{k}^{T} A r_{k} \leq L r_{k}^{T} r_{k}, r_{k}^{T} A^{- 1} r_{k} \leq l^{- 1} r_{k}^{T} r_{k} .

Hence the fraction in the ratio is at least

l / L

, and iteration yields

f (x_{k}) - f (x^{*}) \leq (1 - l / L)^{k} {f (x_{0}) - f (x^{*})} .

When

n = 1

l = L

, so the right side is zero after one iteration: exact line search reaches the solution in a single step.

There are no discussions about this article yet.

There are currently no matching articles.