Non-linear Least Squares Optimization Library for

问题:

I'm looking for a library in C that will do optimization of an objective function (preferrably Levenberg-Marquardt algorithm) and will support box constraints, linear inequality constraints and non-linear inequality constraints.

I've tried several libraries already, but none of them do employ the necessary constraint types for my application:

• GNU GSL (does not support constraints at all)
• cMPFIT (only supports box constraints)
• levmar (does not support non-linear constraints at all)

I am currently exploring NLopt, but I'm not sure if I can achieve a least-squares approach with any of the supplied algorithms.

I find it hard to believe that there's not a single library supporting the full range of constraints in this problem, so I guess I did a mistake somewhere while googling.

I recently discovered I can call Matlab functions from C. While that would solve the problem quite easily, I don't want to have to call Matlab functions from C. It's not fast in my experience.

Any help will be greatly appreciated.

回答1:

Some time ago I was researching the state of C/C++ least squares fitting libraries. I noted down a few links, including the ones you gave and also:

• ALGLIB/optimization -- Lev-Mar with boundary constraints.

• WNLIB/wnnlp -- a constrained non-linear optimization package in C (general optimization, not least squares). Constraints are handled by adding a penalty function.

I haven't used any of the libraries yet, but NLopt seems the most promising for me. It would be great if it had specialized interface and algorithms for (weighted) least-squares fitting.

BTW, does your note about Matlab mean that it has Lev-Mar with non-linear constraints?

回答2:

The approach I finally followed is the following:

• I used NLopt for the optimization and the objective function was constructed to compute the squared error of the problem.

• The algorithm that showed the most promising results was COBYLA (Local derivative-free optimization). It supports box constraints and non-linear constraints. The linear inequity constraints were introduced as non-linear constraints, which should be generally feasible.

Simple benchmarking shows that it does converge a little slower than a Lev-Mar approach, but speed is sacrificed due to the need for constraints.

回答3:

MPFIT: A MINPACK-1 Least Squares Fitting Library in C

MPFIT uses the Levenberg-Marquardt technique to solve the least-squares problem. In its typical use, MPFIT will be used to fit a user-supplied function (the "model") to user-supplied data points (the "data") by adjusting a set of parameters. MPFIT is based upon MINPACK-1 (LMDIF.F) by More' and collaborators.

http://cow.physics.wisc.edu/~craigm/idl/cmpfit.html

回答4:

OPTIF9 can be converted to C (from Fortran) and may already have been by somebody.

If what you mean by box constraints is that it supports upper and lower limits on parameter values, I believe there is a version that does that.

That is a tricky problem, because it means whenever a parameter gets to a boundary, it effectively reduces the degrees of freedom by 1. It can get "stuck on a wall" when you didn't really want it to.

What we've found is that it's better to use an unconstrained minimizer and transform parameters, via something like a log or logit transform, so that in the search space they are unconstrained, but in the model space they are constrained.

As far as the other types of constraints, I don't know, although one option is, as part of your objective function, to make it get really bad when constraints are violated, so the optimizer avoids those areas.

I've found when I have a really flexible set of constraints, if I want a good trouble-free algorithm, I use Metropolis-Hastings. Unless I'm wrong, if it generates a sample that violates constraints, you can simply discard the sample. It takes longer, but it's simple and always works.