# Minimizing 1D convex functions

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.

• Actually, the lowest triangle vertex is a terrible guess. – Geoffrey Irving Mar 4 '14 at 0:58
• Actually I think that depends on your function (for a piecewise linear function it is the exact solution). I think that it should work very well for almost every function, even using it as a procedure to refine between two points. – sebas Mar 4 '14 at 1:10
• The lowest triangle vertex is $(a+b)/2$ if $f$ is quadratic. Ideally I would like second order convergence for smooth functions. – Geoffrey Irving Mar 4 '14 at 1:20
• How much more do you know about the function? 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). – Michael Grant Mar 4 '14 at 3:55
• 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''$. If the billions of problems are closely related, then a warm start from a nearby solution will probably help. – Michael Grant Mar 4 '14 at 13:43

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.