5

since Excel Solver is quite slow to run on thousands of optimizations (the reason being that it uses the spreadsheet as interface), I'm trying to implement a similar (problem-specific) solver in C++ (with Visual Studio 2010, on a Win 7 64-bit platform). I would include the DLL via a Declare statement in VBA and already have experience in doing this, so this is not the problem.

My problem would be minimizing the sum of squared errors between empirical data and a target function which is non-linear but smooth, and the problem would include non-negativity (X>=0) or even positivity constraints (e.g. X>=0.00000001), with X denoting the decision variable.

I'm looking for a robust, proven implementation. It may be part of an established library. For example, I've already looked into what ALGLIB has in store (see http://www.alglib.net/optimization/) and it seems only one of their algorithms accepts bounded constraints. But I don't know what it's worth, though, that's why I'm trying to gather some opinions.

Or, on another note, would it be advisable to augment ALGLIB's Levenberg-Marquardt algorithm with such basic constraints, for example by rejecting every intermediate solution that does not satisfy my constraints? (guess that won't do it, but it's still worth asking)

Steve06
  • 741
  • 2
  • 15
  • 32

3 Answers3

2

There are modifications of the Levenberg-Marquardt method that add support for inequality constraints. I know about one library that implements such an algorithm: levmar (GPL).

If you would like to modify an existing algorithm, rejecting bad solutions won't do, the optimization will likely get stuck. But you can make a variable substitution, e.g. to ensure that X > 0.1 you can use t^2+0.1 instead of X. I use this method as a workaround for the lack of built-in box constraints in my program. Here is a quote from Data fitting in the chemical sciences by Peter Gans that describes it better: https://github.com/wojdyr/fityk/wiki/InequalityConstraints

marcin
  • 3,351
  • 1
  • 29
  • 33
0

We find OPTIF9 and UNCMIN to be the standard methods of choice. You should be able to link them in a library, and call them from C++, if you don't want to bother compiling Fortran.

A way to put limits on the search space is to transform the parameters, such as by a logit function.

Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135
0

Have you looked into the Microsoft Solver Foundation? The express edition is free, and comes with a .NET 4.0 dll. I found it fairly easy to use. On the other hand, I don't know how large of a problem you are talking: there are some limitations in the number of variables in the express edition.

Mathias
  • 15,191
  • 9
  • 60
  • 92