Non-linear least squares with relative constraints on parameters

Dear community,

I'm wondering if anyone has thought about using lsqnonlin to solve non-linear least squares problems with relative constraints on parameter estimates. Whereas it's straightforward to limit parameter estimates in an absolute sense by specifying lower and/or upper bounds, I'm wondering if it's possible to specify parameter values relative to one another.

Specifically, if I'm estimating a vector, x, of parameters, the constraint I'm hoping to impose is that the difference between any two adjacent parameters (elements in x), x i and x i+1, is less than some amount, a.

If this is possible using lsqnonlin, that'd be great. If not, is there another function that might work? Any help would be much appreciated!

Thanks.

Answer 1

[John D'Errico]

The problem as posed is easily solved using fmincon, with LINEAR inequality constraints. Use of nonlinear inequality constraints is patently silly, since that forces fmincon to differentiate those constraints.

So if you want to use fmincon, then just supply a linear inequality constraint for each pair of consecutive parameters, in each direction. (Be careful with the direction of the inequalities. I wrote them below, but fmincon assumes one specific direction.)

Having said that, this is also trivial to solve using lsqnonlin or lsqcurvefit. There is no need to formulate the problem for fmincon. if you can use a nonlinear least squares solver to solve a nonlinear least squares problem, then do so. Avoid using fmincon if you can, since fmincon will be less efficient than a least squares tool. Use the tool that is designed to solve the class of problem, IF you can.

Here all that is needed is to solve a nonlinear least squares problem subject to the constraints that

x(i) - x(i+1) <= delta
x(i+1) - x(i) <= delta

Yes, I know that lsqnonlin won't handle linear inequalities. So transform the problem. The trick is to optimize the DIFFERENCE between successive parameter values. In your objective function, just use cumsum. So the first parameter has no upper or lower bound. all other parameters will be bounded by -delta on the lower end, and by delta on the upper end.

function r = objective(X)
  x = cumsum(X);
  % now work with the parameters x the vector x.
  % compute your vector r, as a function of the vector x.
  ...

end

When you call lsqnonlin, you will set the lower and upper bounds as

   lb = [-inf,repmat(-delta,1,n-1)];
   ub = [inf,repmat(delta,1,n-1)];

So the first element is unbounded, the rest are bounded by delta in EITHER direction. lsqnonlin sees parameters that have only simple bounds, so it is happy. Your objective function will use cumsum internally.

When you get the parameters passed out from lsqnonlin, just use cumsum on them to get the parameters in the form you actually want.

Of course, be careful to pass in starting values to lsqnonlin that will satisfy those bound constraints. But this is easy to do, since you know how the problem is set up.

[ams92]

Thanks for this clever approach. As a newcomer to MATLAB's nonlinear solvers, I appreciate the help. I was unaware of the typical response time & wait on MATLAB Answers community questions, or I'd of course have waited longer before providing an answer. While the solution I'd outlined was a quick fix for a problems with small amounts of data, it's not the most efficient choice. Seeing as you've covered it (the possibility of using fmincon) in your answer, I've removed my original response for the sake of clarity and selected yours as the best answer.

[John D'Errico]

Answers has a limited set of people who answer questions quickly. You would soon see who they are, or find out by checking the list of solvers to see who has the most reputation here. It is very often true that the person who does have the answer to your question might not check in for a few hours, or even a day. And since many of the frequent solvers live in a few specific parts of the world, there are periods of time where little activity goes on here.

So you want to give a question at least a day or so before you accept an answer.

And remember, that when you accept an answer, a student down the line may well decide that the accepted answer is the correct way to solve the problem.