4
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Thank you for good advise, I got the book and reading it. $\endgroup$ – Alexander Jun 12 '12 at 8:03
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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