Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 2 down vote favorite

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

share|improve this question

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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