1d linear regression with inequality constraint

I want to solve a simple 1D linear regression problem:

$\mathbf{y} = m \mathbf{x} + c$

such that $m_{low} < m < m_{high}$ and $c_{low} < c < c_{high}$.

How can I solve this problem? Could this be framed as a linear programming problem?

• You do not have to frame it as a linear programming problem. Just frame it as a standard optimization problem where the solution space of your parameters is constrained. This should work relatively fine because the SSE cost is a rather well-behaved function to begin with. Aug 8 '16 at 9:03

The most straightforward way to solve a constrained regression problem is simply to re-express it as an optimization problem. Indeed most routines solving constrained least squares pose them as quadratic programming tasks (rather than linear) but this is a bit of an overkill for the problem you pose, a standard introductory reference would be Practical Optimization by Gill, Murray, and Wright, see Sect. 4.7 on Methods for Sum of Squares, after that Chapt. 5 then deals with Linear constraints. For this simple a simple optimization routine like R's optim is adequate.

You simply define your cost function myRSS:

myRSS <- function(X,y,beta){ return( sum( (y - X%*%beta)^2 ) ) }


And then your pass it to your favourite solver (here optim's L-BGFS-B routine):

bfgsOptimConst = optim(myRSS, par = c(1,1), X=newMatX, y= newVecY,
method = 'L-BFGS-B',
lower = c(c_low,m_low), uppper = c(c_high, m_high))


Just notice that you need the matrix X and the vectors y and beta to be of the correct dimensions ($N \times 2$, $N\times1$ and $2 \times 1$ respectively for your problem at hand), you also need to provide a feasible solution as a starting point $\beta_0$ for your solution parameters. (I used the $\beta_0 = (1,1)$ but this was just for illustration.)