From: ramin@leland.Stanford.EDU (Ramin Samadani) Newsgroups: sci.math Subject: fitting data, monotonic constraints Date: 12 Jan 1995 09:45:51 -0800 Hi, I am interested in fitting data to a bunch of points, but with the constraint that the fitting function should be monotonically increasing. Is there an easy bookor article to read on this subject ? (its a practical application). For example, if I do a global fit to a 4th order polynomial, how do I force it to be monotonic? If I fit a spline, how do I also force it to be monotonic? Thanks for leads on this. Ramin p.s. I don't read this group, so e-mail would be great. ============================================================================== Date: Tue, 17 Jan 95 13:42:22 -0800 From: Ramin Samadani To: rusin@math.niu.edu Subject: Re: fitting data, monotonic constraints Thanks for your messages. I'm not sure I have enough background to understand what you just sent me (and the message before). How do you get these things about irreducible quadratics??? Also, how is a positive function a sum of squares? A sum of squares of what? Thanks for your hints on this, also, a great paper on interpolation seems to be "monotone piecewise cubic interpolation" by Fritsch and Carlson. Siam J. Num. Anal., April 1980. Ramin ============================================================================== Date: Tue, 17 Jan 95 16:48:44 CST From: rusin (Dave Rusin) To: ramin@nova.Stanford.EDU Subject: Re: fitting data, monotonic constraints >Thanks for your messages. I'm not sure I have enough background to understand >what you just sent me (and the message before). How do you get these things >about irreducible quadratics??? Also, how is a positive function a sum >of squares? A sum of squares of what? Thanks for your hints on this, > >also, a great paper on interpolation seems to be "monotone piecewise cubic >interpolation" by Fritsch and Carlson. Siam J. Num. Anal., April 1980. Not having seen the paper I'd venture to guess it tells you what you want more than I'm about to. But I'll try to clarify a couple of the things I said. The point of the irreducible quadratics is that a function f(x)=x^2+ax+b has no roots if a^2<4b (using the quadratic formula). Therefore a product of such functions has the same property. The converse is also true: a polynomial with no real roots can be written as a product of irreducible quadratics (e.g. f(x)=x^4+2x^3+7x^2+14x+10 has no real roots and we notice it can be factored as (x^2+2,347x+1.161)(x^2-.347x+6.203).) Likewise the argument about squares: if f(x) is any function, then g(x)=f(x)^2 is never negative for any x. Similarly a sum of such functions is never negative (although it might be zero if each of the functions you squaresd is zero for the same x). This viewpoint works equally well for functions of several variables. It was a famous problem (in 1900) to see if every non- negative function could be so written; I think the answer was that it could be. The function above is (x^2+x+1)^2 + (2x+3)^2, for example. So you have a couple of different ways fo describing the functions which are never zero. Either way you get a way of describing all monotonic functions, namely, the antiderivatives of the functions which are never zero. For example, the cubic polynomials which are monotonic are those of the form x^3/3 + ax^2/2 + bx + c where a^2<4b. At this point you need to realize that "curve fitting" means running over all the curves in a set and selecting one which is "best" in some way. The usual regression techniqes define "best" to mean "having the sum of the squares of the differences between the observed and predicted y-coordinates being as small as possible." That definition is used because that leads to the kind of problem we can solve: choosing variables (like the a and b above) which minimize something (like the sums of squares of the errors). You use the multivariate calculus approach to find the best a and b ; when the family of functions you're selecting from is just "f(x)=ax+b" you get really simple linear equations to solve to find a and b. No one thinks about what they're doing, they just ask the computer to find a and b, but that's what's going on. The procedures I suggested to you involved functions like f(x)=x^3/3+ax^2/2+(a^2/4)x + b, which is clearly more complex than f(x) = ax+b, but from a calculus perspective, the problem is only harder in the computations, not the theory. Frankly, if I were you, I'd just plot a simple curve and see if it's monotone. If that one function is clearly not monotone, that suggests that any monotone function you do try to fit to the data is going to be a poor fit, so I'd give up on the monotonicity. But I guess I'd have to know the application before I could commit myself to that. dave ============================================================================== Date: Tue, 17 Jan 95 16:45:10 -0800 From: Ramin Samadani To: rusin@math.niu.edu Subject: Re: fitting data, monotonic constraints Great, thanks, I now understand. Ramin ============================================================================== [The following was _probably_ sent to Ramin as well. - djr] ============================================================================== From: rusin Subject: returned mail for me To: rusin Date: Tue Jan 17 10:24:24 1995 You know, it occured to me after I wrote you that the class of monotonic polynomials is certainly characterized as the set of polynomials whose derivative is a product of irreducible quadratics: (x^2+ax+b) with a^2<4b. Thus your curve-fitting problem can be written as an optimization problem whose domain is a region of n-space (n=degree of polynomials you wish to fit) subject to a bunch of inequalities. This could be solved by Lagrange multipliers. I think this is no easier, and possibly harder, than the method I sent you before, but in my previous letter I had to fudge a little with the characterization of positive derivatives as those which were sums of squares. I realize you were probably looking for something more direct, but just in case you wanted to do it rigorously rather than easily I thought I'd try to correct this oversight in my other letter. dave