# Convergence of step-length in a globally-convergent newton line search method with non-degenerate Jacobian

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! :)

-

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.
 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... – Paul♦ Sep 29 '12 at 0:13 Think about what $p_k$ is and plug that into your formula. – Wolfgang Bangerth Sep 29 '12 at 12:50 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. – Paul♦ Sep 29 '12 at 14:53 Remember that $r(x_k)=\nabla f(x_k)$ and $J(x_k)=\nabla^2 f(x_k)$. – Wolfgang Bangerth Sep 29 '12 at 15:04 Aha! That's the detail I was missing... By substituting these terms into the equation, everything simplifies to unity! :) Thank you so much, Wolfgang! :) – Paul♦ Sep 29 '12 at 18:54