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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – usεr11852
    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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.