# Linear regression analysis where the fit values must be greater than the observed values?

Long story short, I would like to efficiently:

Minimize ||bX-y||2 subject to X ≥ 0 and bX ≥ y

I have an observation that is a single curve (y) in the form of signal intensity vs. frequency. I would like to model this signal as a linear combination of a series of predictor curves in a design matrix, X. My current implementation is using an ordinary least squares analysis where the coefficients of the predictor curves, X, are given by,

b = (XTX)-1XTy

and the fitted values are given by,

ŷ = bX

However, this simple approach minimizes the sum of squared residuals and the fitted curves will always cross the data at some point, which is not physically realistic in the system that I am trying to model. From this, my desired restrictions would be:

bX ≥ y,

b ≥ 0

If anyone could point me in the right direction it would be greatly appreciated.

• Did you think about optimization with one inequality constraint per data point ? – Claude Leibovici Dec 25 '18 at 15:41
• @ClaudeLeibovici I had not initially. Now that I have spent some time researching (Lawson and Hanson, 1974), I think this is the correct method to use. However, I now wish to impose a non-negativity constraint in addition to my original bX> Y constraint. Is it possible to minimize || bX - Y|| subject to X>=0; bX > 0? – burlyhab Dec 28 '18 at 4:08
• If you consider optimization, provided some reasonable guesses for the parameters, you could handle any number of inequality constraints as you wish. I faced this kind of problems long time ago. It was related to the curve fit of some physical properties (small errors) to be fitted to a nonlinear model; for safety and economic reasons we did not want to overestimate the predicted value at any point. It worked very nicely. – Claude Leibovici Dec 28 '18 at 4:15
• @ClaudeLeibovici Forgive me, this may be a question for a different forum. Do you have a recommendation for a computationally efficient method to solve a minimization of this type? – burlyhab Dec 28 '18 at 4:50
• If I properly remember, we used a modified version of subroutine NLPQL which was developed by Schittkowski in the mid 80's. Having a look at klaus-schittkowski.de//NLPQLP.pdf there is an improved version of it and it seems that the code is available at klaus-schittkowski.de – Claude Leibovici Dec 28 '18 at 5:11

If there are n points, this takes $$O(n^3)$$ time since there are $$n(n-1)/2$$ pairs of points and you have to check $$n-2$$ other points for each.
A more computationally effective method, could be to get the convex hull of the data points (which takes $$n\log n$$ time). One of its lines will be above or on all the other points, so this will take $$O(n^2\log n)$$ time.
It would be interesting if a $$O(n^2)$$ or $$O(n)$$ method could be found.