Non-linear Least Squares Optimization Library for C [closed]

Question

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.

Dour

Could you update us on what you've done? Thanks. – Their

I went with NLopt. It supports lots of options and the implementation proved very capable for my project. – Dour

Does NLopt uses Levenberg-Marquardt? – Their

As far as I know / remember, no it does not. – Dour

A question asking about a library that mods haven't closed!?!? There's hope for SO after all... – Pashalik

Answer 1

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.

Dour

Answer 2

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?

Prolocutor

WNLIB sound interesting, I will check it out. As for Matlab, to my knowledge the Lev-Mar algorithm does not support non-linear constraints but you can easily implement a least-square approach to a problem using fmincon(). Thanks for your answer. – Dour

Answer 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

Tarriance

Answer 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.

Gingham