0
$\begingroup$

I am finding minimum of the potential function $f=f_1+f_2$, where $f_i: \mathbb{R}^3\to\mathbb{R}$. I was about to use Levenberg-Marquardt as the quick starting point, since it is already implemented in Eigen which I use. For a reason I don't understand, it requires the dimension of the solution ($\mathbb{R}$ in my case) to be higher or equal to the dimension of the searched space ($\mathbb{R}^3$ here).

The functions are well-behaved, with one global minimum, have continuous derivatives (which are to be computed numerically, for now), and a good initial starting solution is provided.

What would be the algorithm to recommend here, for the initial lazy implementation? Just Newton-Raphson with numerically computed gradient?

$\endgroup$
  • 1
    $\begingroup$ Levenberg-Marquardt is for nonlinear least-square solutions of an (underdetermined) system of equations, not minimizing a functional. If you have sufficiently accurate second derivatives, Newton-Raphson would be my choice (possibly with a trust-region globalization a la Steihaug), otherwise BFGS, nonlinear CG, or just a simple gradient descent with Armijo line search. $\endgroup$ – Christian Clason Aug 14 '14 at 16:49
  • $\begingroup$ I'd just throw a quasi-Newton method at it with a line search. If you can compute Hessians and gradients analytically, do it and use a Newton method. If you can't get a Hessian matrix, use BFGS (or DFP) with analytical or numerical gradients. For a 3-D case, I doubt you'd run into any problems. $\endgroup$ – Geoff Oxberry Aug 15 '14 at 3:58
  • $\begingroup$ Thanks to both of you. Can either of you post it as na anwer so that I accept it? $\endgroup$ – eudoxos Aug 15 '14 at 6:06
  • $\begingroup$ I've removed the c++ and 3d tags, since they turned out to be not really relevant to the question -- if that's not the case, feel free to roll back (and maybe add a remark to the question why 3D is special here). $\endgroup$ – Christian Clason Aug 15 '14 at 8:43
3
$\begingroup$

Levenberg-Marquardt is for nonlinear least-square solutions of an (underdetermined) system of equations (i.e., solving $f(x)=0$ for $f:\mathbb{R}^n\to \mathbb{R}^m$, $m<n$), not for minimizing a functional (i.e., a scalar-valued function -- if the function is not scalar-valued, you can't minimize it, since there's no sensible order on $\mathbb{R}^m$).

From your tag, I assume that "well-behaved" means (strictly) convex, so standard methods should work:

  1. If you have sufficiently accurate second derivatives (either explicitly or as a procedure that evaluates them given a point and direction), Newton-Raphson would be my choice (possibly with a trust-region globalization a la Steihaug).

  2. Otherwise (i.e., you need to approximate derivatives by taking finite differences), try a quasi-Newton method such as BFGS (combined with an Armijo line search); there's a very light-weight C++ implementation based on Eigen (but without line searches).

One thing to watch out for is that methods that use the function values for globalization (trust-region or backtracking line search) can be rather sensitive to errors in derivatives, since they assume the gradient (or the Newton direction) is in fact a descent directions, which might not be the case for the approximate gradient (or Newton direction).

TL;DR: If at all feasible, it's always worth the effort to compute an exact gradient (even for a lazy implementation). For the Hessian, it's not so critical, but if you don't have exact second derivatives, use BFGS instead of computing second-order finite-difference approximations.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Well, one of my favorite algorithms to use for optimization of functions is the Nelder-Mead method. It is a derivative-free method for nonlinear optimization. Depending on you functions it may not be the best method to optimize, but it should probably do the job.

If you have access to matlab, it is implemented there under the name 'fminsearch'.

Also a small note, you say that your two functions both have a single global minimum - be careful, since their sum may not have one.

| cite | improve this answer | |
$\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.