### Tags: 3rd, amtrying, ax3bx2cxd, constraints, fit, increasing, matlab, order, polynomial, programming, setting, suppose

# Problem with Setting Up Constraints

On Programmer » Matlab

13,936 words with 3 Comments; publish: Wed, 07 May 2008 00:55:00 GMT; (20078.13, « »)

I want to fit an "increasing" polynomial to a set of data (x,y)'s.

Suppose the polynomial is of 3rd order i.e.f(x)=ax^3+bx^2+cx+d, I am

trying to use the optimization toolbox with constriant which is the

first derivatives for a given range of x must be at least zero. How

can I setup this constraint in Matlab? Thanks!

*http://matlab.todaysummary.com/q_matlab_48074.html*

All Comments

Leave a comment...

- 3 Comments
- In article <ef1e8ae.-1.matlab.todaysummary.com.webx.raydaftYaTP>, C <abc.matlab.todaysummary.com.abc.com> wrote:
> I want to fit an "increasing" polynomial to a set of data (x,y)'s.

> Suppose the polynomial is of 3rd order i.e.f(x)=ax^3+bx^2+cx+d, I am

> trying to use the optimization toolbox with constriant which is the

> first derivatives for a given range of x must be at least zero. How

> can I setup this constraint in Matlab? Thanks!

I prefer splines for this type of thing. Strongly so,

for reasons you will understand as you read on.

First, I'd need to know if you are asking for a

locally monotone curve or a globally one. Do you

care if a derivative sign change occurs outside of

the domain of your data? I'll assume you only care

about local monotonicity, because the global case

becomes hard for any order beyond a quadratic.

A linear function is simple. You can constrain a

linear function to have a non-negative slope simply

by constraining the coefficient of the linear term

to be greater than or equal to zero. Use lsqlin for

this (from the optimization toolbox.) All this

requires is a bound constraint, something that

lsqlin does handily.

A quadratic function cannot be constrained to be

globally monotone, nor can any even order polynomial.

You can constrain a quadratic to not have a sig

change in the slope over a given (restricted) domain

though. Since f'(x) for quadratic f is linear, then

if that slope is non-negative at both ends of the

interval, then f will indeed be monotone increasing

over that interval. This procedure can also be

accomplished using lsqlin, here you will need a

pair of linear inequality constraints to do it.

Note that I have carefully been using the term

non-negative for slopes, since it is possible to

have a zero slope at some point. Constraints are

always of the >= form or <=. Strict inequalities,

< and >, cannot be set in lsqlin. You could

constrain the slope to be >= some reasonably small

number over some interval.

The cubic case is the first one that gets moderately

interesting. Its also the last one that you can

say very much definite about.

What can we say about a cubic? There do exist cubic

polynomials that are globally monotone. You can

convince yourself of this easily enough. If the

derivative function (a quadratic polynomial) is

everywhere positive, then the cubic has everywhere

a positive sign. It turns out that constraining a

quadratic to be everywhere positive is not trivial

in an lsqlin context, so simpler is to just force

the cubic to be monotone increasing over some

interval.

What does it take to force a cubic to be monotone

over some interval? A nice paper by Fritsch and

Carlson showed a way to do so.

F.N. Fritsch, R.E. Carlson; "Monotone Piecewise Cubic

Interpolation"; SIAM Journal on Numerical Analysis;

1980; Vol. 17; No.2; 238-246

They show that over some interval, if you look at

the slope at each end of the interval, then divide

by the chord slope of the function over that interval,

then you can define constraints which will ensure the

cubic is monotone over that interval. Sadly, these

constraints are not linear ones, so lsqlin is not

directly useful. You can however, approximate the

constraint region by a set of linear constraints,

yielding a polygonal region than lsqlin can deal

with.

This procedure yields what I'll call a sufficient

condition for monotonicity. Since the true region

we needed to approximate was a nonlinear convex set,

any approximation by a polytope will cause some

admissible cubics to lie outside the polytope. (I've

found that you can do a good job though, with not

too many potential polynomials discarded by such an

approximation.) These sufficient conditions for

monotonicity do ensure monotonicity (really only

non-negativity of the slope.)

One can also use an alternative class of constraints.

Just as the previous solution allowed us to impose

a sufficient condition for monotonicity, we can also

impose necessary conditions. Simply constrain the

polynomial to have a positive slope at some set of

(many) points inside the interval of interest. You

might even choose gaussian quadrature nodes for this

set. Essentially, just choose the roots of a chebychev

polynomial of some desired order. The more points,

the better. Each point will become a single linear

inequality constraint, something that lsqlin can

easily handle.

Does this ensure monotonicity? Clearly not. But it

will ensure the curve is never too badly non-monotone.

The necessary form of constraints is the ONLY form

that will work for higher order polynomials. You

cannot apply a trick like the Fritsch and Carlson

one to higher order polynomials.

I'll wind up soon. In fact, I've really come back to

my original statement, that I prefer spline models

over polynomials. The fact is, its trivially easy

(ok, my definition of "trivial" is not the same as

that of most sane individuals) to build a monotone

piecewise linear spline. Even a monotone cubic spline

is not truly that nasty to do. If you need more

flexibility, then you use more knots in the spline.

Enough now. If I keep writing on this subject, I

might never stop. I hope that one day I can offer

a tool to do all of this for you. 'til then...

HTH,

John D'Errico

The best material model of a cat is another, or preferably the same, cat.

A. Rosenblueth, Philosophy of Science, 1945

Those who can't laugh at themselves leave the job to others.

Anonymous

#1; Wed, 07 May 2008 00:56:00 GMT

- In article <ef1e8ae.-1.matlab.todaysummary.com.webx.raydaftYaTP>, C <abc.matlab.todaysummary.com.abc.com> wrote:
- Thanks for your reply. I know Matlab has a function ("pchip") which does the
monotonic interpolation method that you mentioned. In fact, this is the

method that I have been using for my problem. The reason why I decide to fit

one signle function instead of using interpolation is because now I need to

impose certain conditions between some data points and I cannot figure out a

way to implement this in the monotonic interpolation method.

"John D'Errico" <woodchips.matlab.todaysummary.com.rochester.rr.com> wrote in message

news:woodchips-5BBF6E.07252812122005.matlab.todaysummary.com.syrcnyrdrs-01-ge0.nyroc.rr.com...

> In article <ef1e8ae.-1.matlab.todaysummary.com.webx.raydaftYaTP>, C <abc.matlab.todaysummary.com.abc.com> wrote:

>

> I prefer splines for this type of thing. Strongly so,

> for reasons you will understand as you read on.

> First, I'd need to know if you are asking for a

> locally monotone curve or a globally one. Do you

> care if a derivative sign change occurs outside of

> the domain of your data? I'll assume you only care

> about local monotonicity, because the global case

> becomes hard for any order beyond a quadratic.

> A linear function is simple. You can constrain a

> linear function to have a non-negative slope simply

> by constraining the coefficient of the linear term

> to be greater than or equal to zero. Use lsqlin for

> this (from the optimization toolbox.) All this

> requires is a bound constraint, something that

> lsqlin does handily.

> A quadratic function cannot be constrained to be

> globally monotone, nor can any even order polynomial.

> You can constrain a quadratic to not have a sig

> change in the slope over a given (restricted) domain

> though. Since f'(x) for quadratic f is linear, then

> if that slope is non-negative at both ends of the

> interval, then f will indeed be monotone increasing

> over that interval. This procedure can also be

> accomplished using lsqlin, here you will need a

> pair of linear inequality constraints to do it.

> Note that I have carefully been using the term

> non-negative for slopes, since it is possible to

> have a zero slope at some point. Constraints are

> always of the >= form or <=. Strict inequalities,

> < and >, cannot be set in lsqlin. You could

> constrain the slope to be >= some reasonably small

> number over some interval.

> The cubic case is the first one that gets moderately

> interesting. Its also the last one that you can

> say very much definite about.

> What can we say about a cubic? There do exist cubic

> polynomials that are globally monotone. You can

> convince yourself of this easily enough. If the

> derivative function (a quadratic polynomial) is

> everywhere positive, then the cubic has everywhere

> a positive sign. It turns out that constraining a

> quadratic to be everywhere positive is not trivial

> in an lsqlin context, so simpler is to just force

> the cubic to be monotone increasing over some

> interval.

> What does it take to force a cubic to be monotone

> over some interval? A nice paper by Fritsch and

> Carlson showed a way to do so.

> F.N. Fritsch, R.E. Carlson; "Monotone Piecewise Cubic

> Interpolation"; SIAM Journal on Numerical Analysis;

> 1980; Vol. 17; No.2; 238-246

> They show that over some interval, if you look at

> the slope at each end of the interval, then divide

> by the chord slope of the function over that interval,

> then you can define constraints which will ensure the

> cubic is monotone over that interval. Sadly, these

> constraints are not linear ones, so lsqlin is not

> directly useful. You can however, approximate the

> constraint region by a set of linear constraints,

> yielding a polygonal region than lsqlin can deal

> with.

> This procedure yields what I'll call a sufficient

> condition for monotonicity. Since the true region

> we needed to approximate was a nonlinear convex set,

> any approximation by a polytope will cause some

> admissible cubics to lie outside the polytope. (I've

> found that you can do a good job though, with not

> too many potential polynomials discarded by such an

> approximation.) These sufficient conditions for

> monotonicity do ensure monotonicity (really only

> non-negativity of the slope.)

> One can also use an alternative class of constraints.

> Just as the previous solution allowed us to impose

> a sufficient condition for monotonicity, we can also

> impose necessary conditions. Simply constrain the

> polynomial to have a positive slope at some set of

> (many) points inside the interval of interest. You

> might even choose gaussian quadrature nodes for this

> set. Essentially, just choose the roots of a chebychev

> polynomial of some desired order. The more points,

> the better. Each point will become a single linear

> inequality constraint, something that lsqlin can

> easily handle.

> Does this ensure monotonicity? Clearly not. But it

> will ensure the curve is never too badly non-monotone.

> The necessary form of constraints is the ONLY form

> that will work for higher order polynomials. You

> cannot apply a trick like the Fritsch and Carlson

> one to higher order polynomials.

> I'll wind up soon. In fact, I've really come back to

> my original statement, that I prefer spline models

> over polynomials. The fact is, its trivially easy

> (ok, my definition of "trivial" is not the same as

> that of most sane individuals) to build a monotone

> piecewise linear spline. Even a monotone cubic spline

> is not truly that nasty to do. If you need more

> flexibility, then you use more knots in the spline.

> Enough now. If I keep writing on this subject, I

> might never stop. I hope that one day I can offer

> a tool to do all of this for you. 'til then...

> HTH,

> John D'Errico

>

> --

> The best material model of a cat is another, or preferably the same, cat.

> A. Rosenblueth, Philosophy of Science, 1945

> Those who can't laugh at themselves leave the job to others.

> Anonymous

#2; Wed, 07 May 2008 00:57:00 GMT

- Thanks for your reply. I know Matlab has a function ("pchip") which does the
- In article <439f9db5$0$37658$c30e37c6.matlab.todaysummary.com.ken-reader.news.telstra.net>,
"CK" <cf276.matlab.todaysummary.com.hotmail.com> wrote:

> Thanks for your reply. I know Matlab has a function ("pchip") which does t

he

> monotonic interpolation method that you mentioned. In fact, this is the

> method that I have been using for my problem. The reason why I decide to f

it

> one signle function instead of using interpolation is because now I need t

o

> impose certain conditions between some data points and I cannot figure out

a

> way to implement this in the monotonic interpolation method.

What conditions do you need to apply? I may be

able to help.

John

The best material model of a cat is another, or preferably the same, cat.

A. Rosenblueth, Philosophy of Science, 1945

Those who can't laugh at themselves leave the job to others.

Anonymous

#3; Wed, 07 May 2008 00:58:00 GMT

- In article <439f9db5$0$37658$c30e37c6.matlab.todaysummary.com.ken-reader.news.telstra.net>,