Monotonic polynomial fit

[Tiago Falk]

Hello all,
I am trying to fit x to y using 3rd order polynomial fitting. But this
polynomial has to be constrained to be monotonically increasing in the
range min(x) to max(x). I'm wondering if anyone has any code
(preferably Matlab) available that will help me out. I've tried using
(with no success) the lsqlin function from Matlab, but haven't
succeeded. Please help!!!
Thanks for your time

[John D'Errico]

Post by Tiago Falk
Hello all,
I am trying to fit x to y using 3rd order polynomial fitting. But this
polynomial has to be constrained to be monotonically increasing in the
range min(x) to max(x). I'm wondering if anyone has any code
(preferably Matlab) available that will help me out. I've tried using
(with no success) the lsqlin function from Matlab, but haven't
succeeded. Please help!!!
Thanks for your time

Its actually not that hard... (famous last words)

If you look in the paper I cite below, you will find a
convex region which will contain all monotone cubic
polynomial segments. The region has one elliptical
boundary. The paper applies this result to cubic "spline"
interpolation, but it can also apply to a least squares
solution. Merely express this region approximately as a
set of linear inequalities, and you can solve the problem
using lsqlin. If you are willing to put it into fmincon,
then you can define the exact region as a nonlinear
inequality constraint.

The lsqlin solution with linear inequalities approximating
the boundary will result in a sufficient condition for
monotonicity. (i.e., the result will be assuredly monotone,
but there may be some monotone cubic polynomials which
were not allowed by the constraint. It depends upon how
good of an approximation you make.) An alternative is to
sample the polynomial over the region, then constrain the
first derivative of the polynomial at that set of points.
These constraints will be linear in the polynomial
coefficients, but it is possible that the resulting
solution may be slightly non-monotone. Thus this approach
will form a set of necessary conditions for monotonicity.
(It is also very easy to implement using lsqlin.)

You have a choice. If you want to solve it as a "linear"
problem using lsqlin, then you can have either a necessary
or sufficient solution for monotonicity, but not both.
The sufficient solution is the one I strongly prefer,
but it does take more work. I prefer the sufficient
approach because slightly non-monotone makes almost
as much sense to me as being slightly pregnant.

In the event that all of this seems hopelessly, insanely
difficult, respond back to this group and I can put
together a simple code in a few days when I get some
time. In that event, let me know your preference.

F.N. Fritsch, R.E. Carlson; ³Monotone Piecewise Cubic
Interpolation²; SIAM Journal on Numerical Analysis;
1980; Vol. 17; No.2; 238-246

HTH,
John D'Errico

[Tiago Falk]

Mr. D'Errico,

Thank you for all the help. The paper you referenced was very
helpful.
Again, thank you for all your time.
- Tiago
Falk)

Post by Tiago Falk

Post by Tiago Falk
Hello all,
I am trying to fit x to y using 3rd order polynomial fitting.

But

Post by Tiago Falk
this

Post by Tiago Falk
polynomial has to be constrained to be monotonically increasing

in the

Post by Tiago Falk
range min(x) to max(x). I'm wondering if anyone has any code
(preferably Matlab) available that will help me out. I've tried

using

Post by Tiago Falk
(with no success) the lsqlin function from Matlab, but haven't
succeeded. Please help!!!
Thanks for your time

Its actually not that hard... (famous last words)
If you look in the paper I cite below, you will find a
convex region which will contain all monotone cubic
polynomial segments. The region has one elliptical
boundary. The paper applies this result to cubic "spline"
interpolation, but it can also apply to a least squares
solution. Merely express this region approximately as a
set of linear inequalities, and you can solve the problem
using lsqlin. If you are willing to put it into fmincon,
then you can define the exact region as a nonlinear
inequality constraint.
The lsqlin solution with linear inequalities approximating
the boundary will result in a sufficient condition for
monotonicity. (i.e., the result will be assuredly monotone,
but there may be some monotone cubic polynomials which
were not allowed by the constraint. It depends upon how
good of an approximation you make.) An alternative is to
sample the polynomial over the region, then constrain the
first derivative of the polynomial at that set of points.
These constraints will be linear in the polynomial
coefficients, but it is possible that the resulting
solution may be slightly non-monotone. Thus this approach
will form a set of necessary conditions for monotonicity.
(It is also very easy to implement using lsqlin.)
You have a choice. If you want to solve it as a "linear"
problem using lsqlin, then you can have either a necessary
or sufficient solution for monotonicity, but not both.
The sufficient solution is the one I strongly prefer,
but it does take more work. I prefer the sufficient
approach because slightly non-monotone makes almost
as much sense to me as being slightly pregnant.
In the event that all of this seems hopelessly, insanely
difficult, respond back to this group and I can put
together a simple code in a few days when I get some
time. In that event, let me know your preference.
F.N. Fritsch, R.E. Carlson; ³Monotone Piecewise Cubic
Interpolation²; SIAM Journal on Numerical Analysis;
1980; Vol. 17; No.2; 238-246
HTH,
John D'Errico
--
There are no questions "?" about my real address.
The best material model of a cat is another, or
preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945

[Per Sundqvist]

Post by Tiago Falk
Hello all,
I am trying to fit x to y using 3rd order polynomial fitting. But this
polynomial has to be constrained to be monotonically increasing in the
range min(x) to max(x). I'm wondering if anyone has any code
(preferably Matlab) available that will help me out. I've tried using
(with no success) the lsqlin function from Matlab, but haven't
succeeded. Please help!!!
Thanks for your time

Try this non-linear function F(x) also. You use it together with
lsqcurvefit but it require a start guess on the parameters. But it is
a nice analytic expression to give as a semi-empirical formula in a
paper or a report.

%Monotone function F(x), with c0,c1,c2,c3 varitional constants
F(x)= c3 + exp(c0 - c1^2/(4*c2))*sqrt(pi)*...
Erfi((c1 + 2*c2*x)/(2*sqrt(c2))))/(2*sqrt(c2))

%Erfi(x)=erf(i*x) (look mathematica) but the function
%looks much like x^3

%derivative f(x), probability density f(x)>=0
f(x)=dF/dx=exp(c0+c1*x+c2*x.^2)

/Per