# 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? – Costis 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. – hardmath 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? – Geoff Oxberry Jun 11 '12 at 13:11
• Thank you for the comments. I reformulated the question. Hope it sounds better now. – Alexander Jun 11 '12 at 14:01