Minimizing 1D convex functions

Question

I have a one dimensional convex function $$f : [a,b] \to \mathbb{R}$$ and want to find the minimum value $$\min_{a \le x \le b} f(x)$$ I know all derivatives of $f$, so the problem could easily be solved with any 1D minimization method even ignoring the convexity. However, I would like to not ignore the convexity:

Question: How can I best take advantage of convexity to solve my 1D minimization?

For example, the values $f(a),f(b),f'(a),f'(b)$ define a triangular lower bound on the values of $f(x)$ on $[a,b]$, and the lowest vertex of this triangle is likely a good next guess.

Answer 1

If you have derivatives available, no method can beat Newton's method in practice unless you use very specific features of your objective function. This is true whether you want to solve one or a billion problems: solving each one of them is most efficiently done using Newton's method since it is the only one that guarantees quadratic convergence, and this in turn typically leads to convergence to practical accuracies within less than 10 iterations, often significantly less.

Newton's method gets into a bit of trouble occasionally if your objective function is not convex, in which case you need to modify the Hessian appropriately. But, as you say, this is not important in your application.

Answer 2

As requested I'm upgrading my comments to an answer.

To answer the original question it's necessary to understand how much you know about the function. How many derivatives can you readily compute? For instance, strong convexity matters with first-order methods. For second-order methods a similar characteristic of the third derivative probably applies (e.g., self-concordance).

For first-order methods, if you have strong convexity, then gradient search can do quite a good job. If you don't, then consider the so-called "accelerated first-order methods". Theoretically, these methods require Lipschitz continuity, but in practice, you can estimate and adapt the Lipschitz constant and do fine.

For second-order methods, you really can't beat Newton, unless you exploit specific knowledge of your function. That's a big "unless" though.

Another thing we don't know is the computational complexity of computing the values and derivatives. My intuition here is that gradient descent or Newton will be as good as you can expect, with the choice depending on the cost of computing f′′. Unless the second derivative is wickedly expensive, and in your case it sounds like it's not, then Wolfgang wins.

If the billions of problems are closely related, then a warm start from a nearby solution will probably help, especially if you can start within the region of quadratic convergence for Newton.