Math Minimization library and methods (in C++)?

[Aragornthe5th]

Greetings to all,
I have an optimization problem I’m trying to solve. I have 3 variables (basically the position of sphere in X, Y, Z), and I have a cost function I want to minimize. I do not have a way of getting the derivative directly (although I could use something like forward-difference if I have to). So far, I’ve been using MINPACK and lmdif function, but it’s very sensitive to the starting position.
Can anyone suggest a decent, efficient algorithm for this kind of problem, and moreover can anyone suggest any libraries that are known to work correctly and efficiently? I’m using C++ and Visual Studio. Method-wise, I’m considering Simplex, BFGS, or Simulated Annealing, but, again, I’m not sure what libraries to go with…
Right now, I just want to get it to work well with the artificial, clean data, but the final problem will have to deal with somewhat noisy data AND an additional parameter (the radius of the sphere, which also has a size constraint). That said, anything that can also handle the latter conditions robustly as well would be excellent.
If anyone could provide any assistance, it would be very greatly appreciated.
Sincerely,
Michael

 

[CycloWizard]

You can use BFGS to solve your problem, though if your cost function is sensitive to the initial guess, a Levenberg-Marquadt alorigthm (similar to BFGS but takes larger steps at first to move towards the minimum more quickly in some cases where the objective function is flat far from the optimum. This is one possibility to initial point sensitivity, with the other being the presence of local optima. It's impossible to say which might be the problem (or whether it's something else) without knowing what the cost function is, but if it is convex, then the BFGS should have great convergence characteristics.

As far as the constraints go, I highly recommend enforcing constraints using a penalty function like the Courant-Beltrami function. I've never had a problem where this didn't work very well, though I'm sure there are some cases where it could be difficult to apply.

There could also be better optimization algorithms, but without knowing the characteristics of the problem or cost function, I can't really make any recommendations.

 

[Aragornthe5th]

Thanks for the reply!

I've been using Levenberg-Marquadt so far (pretty much what MINPACK implements to my knowledge), but it's still pretty sensitive to the starting point. I will look into BFGS though.

I tried digging around for information on the Courant-Beltrami function, but I'm not coming up with much (although I have been finding data on penalty/barrier functions in general, which I'm reading now). Can you recommend anything that goes over that function specifically?

Again, thanks for the help.

 

[CycloWizard]

Thanks for the reply!

I've been using Levenberg-Marquadt so far (pretty much what MINPACK implements to my knowledge), but it's still pretty sensitive to the starting point. I will look into BFGS though.

In almost all cases, the LM algorithm will be less sensitive to your initial guess than the BFGS. I can't even think of any case where this wouldn't be true. Therefore, I would probably recommend trying a different method or reformulating your cost function to try to approach a convex function. The other option is to lower the tolerance for convergence, as this may help avoid the problems you're having with finding false optima.

I tried digging around for information on the Courant-Beltrami function, but I'm not coming up with much (although I have been finding data on penalty/barrier functions in general, which I'm reading now). Can you recommend anything that goes over that function specifically?

Again, thanks for the help.

The Courant-Beltrami penalty function is simply k*g_i^2, where g_i is the violation of the i^th constraint (0 if no violation or whatever amount by which it is violating the constraint otherwise) and k is a large constant (arbitrary, but 10^8 or 10^12 should work for most cases). Just add this to your cost function for each constraint and you should be good to go. Squaring it ensures convexity. If this doesn't lead to constraint enforcement, you can also employ a barrier method, but I've never really had a problem with this.