enforcing a monotonic increasing quadratic
Turgay
I have a data that look very much like quadratic. I know that the y values should always be increasing. However, there is some noise in the data and because of that y values are sometimes increasing and decreasing. I would like to fit a quadratic curve to this data and want to force the fitted curve to be monotonically increasing.
Any easy ways to do it other than solving a nonlinear programming problem with a constraint?
Thank you very much.
--Turgay
TideMan
What's wrong with the standard Matlab function polyfit?
Greg
Every quadratic contains a monotononically increasing part
and a monotonically decreasing part separated by a point of
zero slope.
Therefore just fit a quadratic without constraints.
If the point of zero slope lies within the range of your data,
then rethink what you really want and need.
Hope this helps.
Greg
John D'Errico
I would suggest using a tool designed to solve this
class of problem. Use my SLM toolbox from the file
exchange. It will allow you to fit a monotone spline
curve through the data. While it is not capable of
fitting a quadratic, the following example fits a single
cubic segment that is both monotone increasing, and
has positive curvature over the domain.
x = rand(20,1);
y = exp(x) + randn(size(x))/10;
slm = slmengine(x,y,'knots',[0 1],'plot','on',...
'increasing','on','concaveup','on','result','pp')
slm =
form: 'pp'
breaks: [0 1]
coefs: [-0.38614 1.2661 0.673 1.0304]
pieces: 1
order: 4
dim: 1
prescription: [1x1 struct]
The nice thing is the SLM tools allow you to do much
more complex curve fits too. The only requirement is
that SLM uses the optimization toolbox. Find SLM
here:
http://www.mathworks.com/matlabcentral/fileexchange/24443
HTH,
John
Turgay
Thanks for the response. You summarize the problem very well.
In fact, yes, the point of zero lies within the range of my data. However, I know that it should not be the case in reality (in reality, it should be monotonically increasing) and this is due to a noise. That is why I cannot use regular polyfit.
Any suggestions for that?
Thanks again.
--Turgay
Greg <he...@alumni.brown.edu> wrote in message <66ab3829-d303-4b92...@d21g2000vbm.googlegroups.com>...
John D'Errico
> Hello Greg,
>
> Thanks for the response. You summarize the problem very well.
>
> In fact, yes, the point of zero lies within the range of my data. However, I know that it should not be the case in reality (in reality, it should be monotonically increasing) and this is due to a noise. That is why I cannot use regular polyfit.
>
> Any suggestions for that?
I already showed you how to solve it for the cubic
case, IF you have the optimization toolbox.
Without the optimization toolbox, you will need
to use a constrained optimizer, commonly found
in the optimization toolbox.
John
Bruno Luong
>
> Thanks for the response. You summarize the problem very well.
>
> In fact, yes, the point of zero lies within the range of my data. However, I know that it should not be the case in reality (in reality, it should be monotonically increasing) and this is due to a noise. That is why I cannot use regular polyfit.
>
> Any suggestions for that?
>
Why not using fmincon to fit the data with the constraint
-b/(2*a) <= min(xi)
Bruno
John D'Errico
If you have the optimization toolbox, fmincon is wild
overkill. Use lsqlin. Constrain the first derivative to be
non-negative at both ends of the domain of interest.
The constraints and the problem are both linear, so
lsqlin is the correct choice. This will ensure the
quadratic is monotone increasing over that interval.
John
Turgay
Hello John,
Thanks for your suggestion. I think your toolbox is a great one, but did not provide a good fit to my data. I am pasting my data below, if it would give you a better idea.
Can I do any better than this fit?
Thanks..
--Turgay
40.0000 0.0584
40.5000 0.0575
41.0000 0.0577
41.5000 0.0560
42.0000 0.0573
42.5000 0.0575
43.0000 0.0584
43.5000 0.0580
44.0000 0.0586
44.5000 0.0583
45.0000 0.0582
45.5000 0.0587
46.0000 0.0594
46.5000 0.0584
47.0000 0.0610
47.5000 0.0602
48.0000 0.0597
48.5000 0.0604
49.0000 0.0605
49.5000 0.0611
50.0000 0.0610
50.5000 0.0613
51.0000 0.0612
51.5000 0.0611
52.0000 0.0616
52.5000 0.0613
53.0000 0.0617
53.5000 0.0610
54.0000 0.0617
54.5000 0.0616
55.0000 0.0609
55.5000 0.0612
56.0000 0.0603
56.5000 0.0605
57.0000 0.0613
57.5000 0.0599
58.0000 0.0603
58.5000 0.0595
59.0000 0.0609
59.5000 0.0607
60.0000 0.0605
60.5000 0.0615
61.0000 0.0622
61.5000 0.0616
62.0000 0.0625
62.5000 0.0612
63.0000 0.0625
63.5000 0.0623
64.0000 0.0628
64.5000 0.0627
65.0000 0.0637
65.5000 0.0636
66.0000 0.0645
66.5000 0.0638
67.0000 0.0648
67.5000 0.0653
68.0000 0.0652
68.5000 0.0652
69.0000 0.0663
69.5000 0.0656
70.0000 0.0665
70.5000 0.0664
71.0000 0.0673
71.5000 0.0673
72.0000 0.0676
72.5000 0.0674
73.0000 0.0689
73.5000 0.0689
74.0000 0.0700
74.5000 0.0701
75.0000 0.0710
75.5000 0.0709
76.0000 0.0734
76.5000 0.0725
77.0000 0.0743
77.5000 0.0732
78.0000 0.0746
78.5000 0.0752
79.0000 0.0765
79.5000 0.0771
80.0000 0.0788
80.5000 0.0792
81.0000 0.0802
81.5000 0.0810
82.0000 0.0821
82.5000 0.0833
83.0000 0.0856
83.5000 0.0869
84.0000 0.0889
84.5000 0.0895
85.0000 0.0920
85.5000 0.0922
86.0000 0.0947
86.5000 0.0965
87.0000 0.0990
87.5000 0.1015
88.0000 0.1039
88.5000 0.1064
89.0000 0.1090
89.5000 0.1111
90.0000 0.1138
90.5000 0.1171
91.0000 0.1200
91.5000 0.1245
92.0000 0.1268
92.5000 0.1314
93.0000 0.1346
93.5000 0.1403
94.0000 0.1411
94.5000 0.1501
95.0000 0.1486
95.5000 0.1579
96.0000 0.1571
96.5000 0.1694
97.0000 0.1631
97.5000 0.1762
98.0000 0.1680
98.5000 0.1833
99.0000 0.1775
99.5000 0.1775
John D'Errico
> "John D'Errico" <wood...@rochester.rr.com> wrote in message <h8ntm5$5fb$1...@fred.mathworks.com>...
> > "Turgay " <a...@b.com> wrote in message <h8nt41$37$1...@fred.mathworks.com>...
> > > Hello Greg,
> > >
> > > Thanks for the response. You summarize the problem very well.
> > >
> > > In fact, yes, the point of zero lies within the range of my data. However, I know that it should not be the case in reality (in reality, it should be monotonically increasing) and this is due to a noise. That is why I cannot use regular polyfit.
> > >
> > > Any suggestions for that?
> >
> > I already showed you how to solve it for the cubic
> > case, IF you have the optimization toolbox.
> >
> > Without the optimization toolbox, you will need
> > to use a constrained optimizer, commonly found
> > in the optimization toolbox.
>
> Hello John,
>
> Thanks for your suggestion. I think your toolbox is a great one, but did not provide a good fit to my data. I am pasting my data below, if it would give you a better idea.
>
> Can I do any better than this fit?
>
You are truly kidding yourself if you really think
that a quadratic polynomial will give you a better
fit, or even a reasonable fit on this data.
The call below will fit a monotone cubic, with
positive curvature over the entire range. It will
have much the character of a quadratic, yet be
more flexible.
slm = slmengine(x,y,'plot','on','knots',2,'increasing','on','concaveup','on')
Even so, that fit is poor. But just wanting a fit
to be better will not make it so. You cannot force
it to do arbitrarily well.
However, the virtue of the SLM tools is that with
only a minimal change, to three equally spaced
knots, the following call will fit your data VERY
nicely.
slm = slmengine(x,y,'plot','on','knots',3,'increasing','on','concaveup','on')
The result is a least squares spline with two
monotone segments. An even nicer feature of this
code is that you could use more knots and still
get essentially the same result. The default of 5
equally spaced knots will fit most curves nicely,
and will be insensitive to exactly where the curve
must bend.
slm = slmengine(x,y,'plot','on','increasing','on','concaveup','on')
I don't know what you think was not satisfactory
about SLM here, yet you want to try to fit a simple
single monotone quadratic polynomial.
John
Turgay
Thank you very much for your help!
--Turgay
"John D'Errico" <wood...@rochester.rr.com> wrote in message <h8o3c1$bi7$1...@fred.mathworks.com>...
John D'Errico
> John, in fact, I was planning to use a high order polynomial fit, but just said quadratic to simplify the case. However, you convinced me that the cubic spline least square fitting model makes a much better job than a higher order polynomial..
>
> Thank you very much for your help!
Actually, it is (trivially) easy to enforce monotonicity
on a quadratic.
Enforcing monotonicity on a cubic takes something
extra, but it is doable, since SLM does exactly that.
Enforcing monotonicity on a higher order polynomial
gets more nasty. The best you can do is to enforce a
set of necessary conditions for monotonicity, but these
conditions are not sufficient. So typically one ends up
with a curve that has a small non-monotone segment
for that case.
SLM is definitely the solution for this class of problems.
John