# Line search for Newton method

If we want to solve nonlinear minimization problem

$$\min_{x} f(x),$$

making least-squares assumption and using Gauss-Newton method so that at k$th$ iteration we have:

$$J_k^T J_k p_k = - J_k^T r_k,$$

with vector $r$ being residual and matrix $J$ Jacobian.

We then update $x$ in the following way:

$$x_{k+1} = x_k + \alpha p_k,$$

where $\alpha \in (0, 1]$

The question is how to find $\alpha$ such that $f(x_{k+1}) = min$

In other words, what step length calculating strategy would be good enough taking into account $f$ and $f'$ are expensive to compute and highly nonlinear?

I'm aware of methods that approximate this problem with polynomial, e.g. in case of quadratic approximation:

$$p_0 + p_1 \alpha + p_2 \alpha^2 = min$$

where $p_0 = f(x_k), p_1 = f'(x_k), p_2 = f(x_k + \alpha p_k)$

But I'm wondering what are the other options to try? Can somebody point me to a good overview or shortly write down different techniques.

• Your polynomial seems to be essentially a Taylor expansion of $f$ at $x_k$. So $p_0 = f(x_k)$, but $p_1$ would have to be $\frac{f'(x_k)}{2}$, etc. So, you would need to evaluate $f$ once, but also $f'$, $f''$, etc. Do you have the derivatives of $f$ available? Jun 11 '12 at 11:11
• What about the cost of computing $f'(x)$? If $f$ is expensive to evaluate, $f'$ might be equally expensive or perhaps much more so. If you want to stick to function evaluations without derivatives, perhaps a Golden Section approach or variants is appropriate. Jun 11 '12 at 11:12
• What would you like to solve? Do you have a specific problem at hand that you would like to solve? Or are you developing a novel method?
– Ali
Jun 11 '12 at 11:19
• Given that there exist many established rules for determining step-size, I'm curious as to why you are deriving another one. What is your goal here? Jun 11 '12 at 13:11
• Thank you for the comments. I reformulated the question. Hope it sounds better now. Jun 11 '12 at 14:01

## 2 Answers

This is discussed in great detail in the excellent book by Nocedal and Wright on nonlinear optimization. I can't summarize the method better than they describe it.

• Thank you for good advise, I got the book and reading it. Jun 12 '12 at 8:03

Popular, simple to implement line search strategies are doubling and backtracking, but they need often more function values than strictly needed. Interpolation schemes as you describe them need safeguards to be efficient, but all (or at least most) currently used schemes are based on some form of interpolation.

The most used high quality line search (enforcing the Wolfe condition) is the one by More and Thuente, http://www.mcs.anl.gov/research/projects/tao/src/linesearch/impls/morethuente/morethuente.c which uses safeguarded cubic Hermite interpolation and is accompanied by a thorough theoretical analysis. http://www.ii.uib.no/~lennart/drgrad/More1994.pdf

• Thank you for the PDF. I will get to it once I read Nocedal and Wright's chapter about step length search. Jun 12 '12 at 8:03
• The link for the implementation is not working anymore. Where can I find this code now?
– Hari
May 17 '16 at 16:27
• @haripkannan: The More-Thuente line search code is now here: mcs.anl.gov/petsc/petsc-master/src/tao/linesearch/impls/… May 17 '16 at 19:36