2
$\begingroup$

I'm working on a problem given in Nocedal & Wright's Numerical Optimization 2nd Edition, pg 303 Exercise 11.7:

Consider a line-search newton method in which the step length $\alpha_k$ is chosen to be the exact minimizer of the merit function $f(\cdot)$; that is,

$$\alpha_k = argmin_\alpha [f(x_k-\alpha J^{-1}(x_k)r(x_k))]$$

Show that if $J(x)$ is non-singular at the solution $x^*$, then $\alpha_k\rightarrow 1$ as $x_k\rightarrow x^*$.

In this problem, we seek $x^*$ such that $r(x^*)=0$, where $r:R^n\rightarrow R^n$ and use a merit function $f(x)$ to globalize the convergence of newton's method with a line search.

I'm trying to work this proof out on my own, but I've run into some difficulties. First of all, I understand that the newton direction $\Delta x_k =-J^{-1}(x_k)r(x_k)$ is a descent direction. Also, if we (theoretically) chose the step length $\alpha_k$ as above, then the new step should satisfy the sufficient decrease condition (Armijo condition):

$$f(x_k+\alpha_k\Delta x)\le f(x_k)+c\alpha_k\nabla f(x_k)^T\Delta x$$ for some $0<c\le1$.

I understand that in practice, we try using the full newton step $\alpha_k=1$ first. If the newton step doesn't produce sufficient decrease, then we search back until sufficient decrease is met. I'm thinking that the fact that the jacobian being non-degenerate implies that there exists a ball around $x^*$ such that the full newton step always satisfies armijo's condition. Thus, as we get closer to the root, the newton step is enough to ensure sufficient decrease. However, I'm not entirely sure that such a ball exists.

I've also tried assuming that $\alpha_k\rightarrow a\ne1$ as $x_k\rightarrow x^*$, but the search for a contradition is somewhat mysterious to me.

Any help with this would be greatly appreciated! :)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

You misread the question. It isn't talking about any Armijo or sufficient decrease condition. It says assume that we compute $\alpha$ as in the formula. Then show that if the iteration converges, i.e., $x_k\rightarrow x^\ast$ that necessarily $\alpha\rightarrow 1$.

The proof of this statement is a simple application of Taylor expansion. If $x_k\rightarrow x^\ast$ then $f(x)$ is approximated better and better in a neighborhood of $x_k$ by a quadratic Taylor approximation whose minimum is attained at a point that corresponds to exactly $\alpha=1$. Simply form the Taylor expansion of $f(x_k+\alpha p_k)$ around $x_k$ with the given $p_k$ and see what happens.

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ The quadratic taylor expansion is $f(x_k+\alpha p_k)=f(x_k)+\alpha\nabla f(x_k)\cdot p_k +\frac{\alpha^2}{2}p_k\cdot\nabla^2 f(x_k) \cdot p_k$. Since $\alpha$ is chosen as the minimum, $\alpha = -\frac{\nabla f(x_k)\cdot p_k}{p_k\cdot\nabla^2 f(x_k) \cdot p_k}$. But as $x_k\rightarrow x^*$, we get an indeterminate form $\frac{0}{0}$. Should I use l'hoptical's rule at this point? It seems a bit too complicated for that... there must be a simpler way... $\endgroup$
    – Paul
    Commented Sep 29, 2012 at 0:13
  • 1
    $\begingroup$ I can see that $p_k$ is simply $-J^{-1}(x_k)r(x_k)$. So when I substitute, I obtain $\alpha = \frac{\nabla f(x_k)\cdot J^{-1}(x_k)r(x_k)}{r^T(x_k)J^{-T}(x_k)\cdot\nabla^2 f(x_k) \cdot J^{-1}(x_k)r(x_k)}$. But as $x_k\rightarrow x^*$, $r(x_k)\rightarrow 0$ (yielding an indeterminate form). Unless I can somehow cancel terms from the numerator & denominator or use l'hopital's rule, I can't see how else to proceed. $\endgroup$
    – Paul
    Commented Sep 29, 2012 at 14:53
  • 1
    $\begingroup$ Remember that $r(x_k)=\nabla f(x_k)$ and $J(x_k)=\nabla^2 f(x_k)$. $\endgroup$
    – Wolfgang Bangerth
    Commented Sep 29, 2012 at 15:04
  • 1
    $\begingroup$ The last piece you were missing in the proof now was that in reality, of course, the function $f$ has more terms in the Taylor expansion than just those up to quadratic one. So while $\alpha=1$ is the exact minimizer of the quadratic approximation, the real minimizer of $f$ is at an $\alpha$ different than that (if it weren't we wouldn't need to do any line search to begin with). However, Taylor's theorem says that as $p_k$ becomes smaller and smaller, the higher order terms become smaller and smaller. Consequently, the minimum of $f$ moves toward that of its quadratic approximation. $\endgroup$
    – Wolfgang Bangerth
    Commented Sep 29, 2012 at 20:22
  • 1
    $\begingroup$ @LCFactorization: For (i), one usually uses a backtracking line search, i.e., one tries $\alpha=1$, then $\alpha=2/3$, then $\alpha=(2/3)^2$, etc. For (ii), try Taylor expansion again :-) $\endgroup$
    – Wolfgang Bangerth
    Commented Dec 23, 2013 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.