Non-linear Least Squares Optimization Library for C [closed]
We don’t allow questions seeking recommendations for books, tools, software libraries, and more. You can edit the question so it can be answered with facts and citations.
Closed 5 years ago.
Improve this questionI'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.
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?
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.
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
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.
精彩评论