Help deciding between cubic and quadratic interpolation in line search

Question

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.

Answer 1

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.

Answer 2

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).