5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, the lowest triangle vertex is a terrible guess. $\endgroup$ – Geoffrey Irving Mar 4 '14 at 0:58
  • $\begingroup$ 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. $\endgroup$ – sebas Mar 4 '14 at 1:10
  • $\begingroup$ The lowest triangle vertex is $(a+b)/2$ if $f$ is quadratic. Ideally I would like second order convergence for smooth functions. $\endgroup$ – Geoffrey Irving Mar 4 '14 at 1:20
  • 3
    $\begingroup$ 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). $\endgroup$ – Michael Grant Mar 4 '14 at 3:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Grant Mar 4 '14 at 13:43
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

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.