9
$\begingroup$

I'm performing a line search as part of a quasi-Newton BFGS algorithm. In one step of the line search I use a cubic interpolation to move closer to the local minimizer.

Let $f : R \rightarrow R, f \in C^1$ be the function of interest. I want to find an $x^*$ such that $f'(x^*) \approx 0$.

Let $f(x_k)$, $f'(x_k)$, $f(x_{k+1})$ and $f'(x_{k+1})$ be known. Also assume $0\le x_k<x^*<x_{k+1}$. I fit a cubic polynomial $Q(x)=ax^3+bx^2+cx+d$ so that $Q(0)=f(x_k)$, $Q'(0)=f'(x_k)$, $Q(x_{k+1}-x_{k})=f(x_{k+1})$ and $Q'(x_{k+1}-x_{k})=f'(x_{k+1})$.

I solve the quadratic equation: $(1): Q'(x^*-x_k) = 0$ for my sought $x^*$ using the closed form solution.

The above works well in most cases, except when $f(x)=\mathcal{O}(x^2)$ as the the closed form solution for $(1)$ divides by $a$ which becomes very close to or exactly $0$.

My solution is to look at $a$ and if it is "too small" simply take the closed form solution for the minimizer of the quadratic polynomial $Q_2(x)=bx^2+cx+d$ for which I already have the coefficients $b,c,d$ from the earlier fit to $Q(x)$.

My question is: How do I devise a good test for when to take the quadratic interpolation over the cubic? The naive approach to test for $a \equiv 0$ is bad due to numerical reasons so I'm looking at $|a| < \epsilon\tau$ where $\epsilon$ is the machine precision, but I'm unable to decide a good $\tau$ that's scale invariant of $f$.

Bonus question: Are there any numerical issues with using the coefficients, $b,c,d$, from the failed cubic fit or should I perform a new quadratic fit with appropriate way of calculating the coefficients?

Edit for clarification: In my question $f$ is actually what is commonly referred to as $\phi(\alpha)=f(\bar{x}_k+\alpha \bar{p_k})$ in literature. I just simplified the question formulation. The optimization problem I'm solving is non-linear in 6 dimensions. And I'm well aware that Wolfe conditions are enough for BFGS line search hence stating that I was interested in $f'(x^*) \approx 0$; I'm looking for something that'll satisfy strong Wolfe conditions and taking the minimizer of the cubic approximation is a good step along the way.

The question was not about BFGS, but rather how to determine when the cubic coefficient is small enough that a quadratic approximation is more appropriate.

Edit 2: Update notation, equations are unchanged.

$\endgroup$
4
$\begingroup$

Hmm... cubic interpolation is not unheard of for line search, but typically overkill.

If I'm reading your problem correctly, $x$ is just a scalar? In this case BFGS is probably not the most efficient way of solving your problem. Scalar optimization algorithms like Brenth's method are likely to solve your problem faster.

There are a number of line search algorithms for BFGS. For my own applications, using the memory limited BFGS (L-BFGS) this linesearch works very well. Remember that you only need to satisfy the Wolfe conditions, and you're likely not gaining much by finding the exact minimizer.

Anyway, to actually answer your question: I would consider simply switching to the quadratic polynomial if solving the cubic one yields "bad" values such as NaN or Inf (as is done here).

I'm not quite sure what you mean by using $b,c,d$? These coefficients for the cubic fit will not be the same as for the quadratic fit so you can't reuse them.

Lastly, you may want to use $f(x_{k-1})$ , rather than $f(x_0)$, as your function will (probably) only be approximately cubic or quadratic locally, and $x_k$ and $x_{k-1}$ should be closer to each other (and the solution) than $x_0$.

Hope this helps.

$\endgroup$
  • $\begingroup$ Edited for clarity. By "using $b,c,d$" I mean that I did a cubic fit to $Q(x)=ax^3+bx^2+cx+d$ and found that $a\equiv 0$ thus I have $Q(x)=bx^2+cx+d$ which is already a quadratic polynomial. And the question was if the coefficients $b,c,d$ obtained for this fit are sensible to use for doing an interpolation or if I should re-calculate new coefficients for a typical quadratic fit. $\endgroup$ – Emily L. May 27 '14 at 9:32
  • $\begingroup$ Ahh, right, ofcourse. I don't see any problem in using the coefficients from a numerical point of view. The only point where I think it would matter, is very close to the solution where you would terminate anyway. $\endgroup$ – LKlevin May 27 '14 at 14:00
  • $\begingroup$ Can you motivate your answer with calculating the cubic and checking for "bad" values? Why is it safe to do when $a << b$ or $a\approx 0$? $\endgroup$ – Emily L. May 27 '14 at 14:52
  • $\begingroup$ When $a \approx 0$, $b,c$ and $d$ will be approximately the ones for the quadratic case. As the BFGS linesearch is quite robust, you should be ok using these, even if they're not completely accurate. As long as you obey the Wolfe conditions you will get convergence. As for the "bad" values, as long as the computer can accurately do the calculations to the precision you need, everything is good. When it can't, you'll start seeing inf and NaN. $\endgroup$ – LKlevin May 27 '14 at 20:46
4
$\begingroup$

There is a paper by Moré, implemented by Nocedal, about that:

Jorge J. Moré and David J. Thuente. 1994. Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 3 (September 1994), 286-307. DOI http://dx.doi.org/10.1145/192115.192132 (preprint).

$\endgroup$
  • $\begingroup$ Welcome to SciComp.SE! I formatted your post to make it easier to find the paper. If you can find a link to Nocedal's implementation, that would be helpful. $\endgroup$ – Christian Clason Jan 28 '16 at 13:42

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.