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; (20062.50, « »)

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!

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
    • 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
    • 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