Can we use linear regression to define the objective function in linear programming?

Question

This is a general question about how linear programming is used in the analytics community.

Is it common, or feasible to use linear regression (or perhaps even more complex models like regression trees) to act as the objective function in a linear program?

I'm interested in statistically deriving linear models of complex phenomena (i.e energy transfer through a surface) and finding optimal combinations of the variables using some optimization methods. Here's an example to clarify my question.

** UPDATED (SO THERE'S NO TRIVIAL SOLUTION) **

Let's say I fit a regression to some heat transfer data, and derive a regression line that can predict the mechanical heating of a room (Qh).

So my regression might look like this:

Qh = b0 + (b1 * km) + (b2 * kg) + (b3 * Am) + (b4 * Ag) + (b5 * dT) + (b6 * Qr)

Where:

Qh = Mechanical heating of the room (Wh)
Qr = Solar radiation flux transmitted through glass (W/m2)
km = Conductance of masonry (low) (W/m2/K)
kg = Conductance of glass (high) (W/m2/K)
Am = Area of masonry (m2)
Ag = Area of glass (m2)
dT = Temperature difference between outside and inside (K)
b0, b1, b2, b3, b4, b5, b6 = regression coefficients.

Solving the regression might give us something like this:

Qh = 1 + (2 * km) + (3 * kg) + (4 * Am) + (5 * Ag) + (6 * dT) + (7 * Qr)

(Note that I'm deliberately not going to use variables to represent the regression weights since they're not variables in this case, the regression has been solved so they are constants).

I would like to find the optimal combination of the wall/glass area that reduces mechanical heating of the room. So the variables for the linear program are (Am, Ag) and we assume everything else is a constant.

This problem is somewhat tricky since, reducing the (high conductance) glass area will reduce heat loss through the wall, and reduce mechanical heating - but will also reduce the transmitted solar radiation that also will reduce mechanical heating.

Can I therefore create a linear program that finds this for me?

In my linear program, this new optimization problem would be represented as:

Objective_function = min(Qh = 1 + (2 * km) + (3 * kg) + (4 * Am) + (5 * Ag) + (6 * dT) + (7 * Qr))   
Variables = Am, Ah (everything else would be a constant determined by the user).
Constraints: 0 < Am < 10; 0 < Ag < 10; Am + Ag = 10.0  

** END UPDATE **

Could I use my regression as a simulation (aka surrogate model) and find the optimal combination of a the variables this way via linear programming? My sense is that a linear program would be uniquely suited for this kind of problem, since it can only represent linear relationships.

However, after some google/stack overflow searches, I haven't been able to find any examples of this particular combination. I'm getting a lot of hits about using linear programming to optimize the regression itself (i.e to minimizing the cost), but not about it's use as the objective function.

Is this just because the use of regressions in linear programming is so obvious, and self-evident no one needs to mention it explicitly? Or am I missing something about why regressions aren't used in linear programming?

Answer 1

You seem to describe a case of linear programming where there is uncertainty in the objective function (and you could generalize this and have uncertainty in the linear boundaries as well).

Could I use my regression as a simulation (aka surrogate model) and find the optimal combination of a the variables this way via linear programming?

No.

Doing this would mean that you fix the linear programming problem and ignore the uncertainty that is inherent to the regression problem.

Yes.

You can do that (and probably many people do it, a two-step approach is simpler and more practical), but it might not be the best way to solve your problem.

What your problem/situation is that is actually not so much clear in your question. But, you may imagine that one has more specific wishes regarding the cost function that is optimized in the regression step. For instance it could be that we do not wish to minimize the residuals of the regression line, but instead we wish to minimize the expectation value of the objective function.

---

Example

In your example case the solution is always at the end points. The uncertainty in the equations defining the linear programming problem is not so relevant for the solution of the problem.

We can however come up with an alternative problem where there is a more clear discrepancy between the minimization of the regression problem (minimizing the sum of squares of the residuals) and plugging that solution into the linear programming, or minimizing more holistically the outcome of the linear programming.

Let's use for this type of example the following cost function (which is to be minimized):

$$y = \frac{1}{3} x^3 - a x$$

This problem may look contrived, but we choose it because it is easy to see that the optimum of the function $y(x)$ occurs in the point $x=\sqrt{a}$.

So for some given set of measurements of $y$ (dependent variable) given several $x$ (independent variable) we could solve the regression problem and say that the solution is $\hat{x}_{min}=\hat{a}^{0.5}$, with the objective value $\hat{y}_{min}=\hat{a}^{1.5}$

But... that is an optimization for the value of $\hat{a}$.

• We might, instead, want to minimize the solution for $\hat{x}_{min}$ or $\hat{y}_{min}$. The sample distributions of these values may not need to be nice symmetric functions around the mean (they are different from the estimate of $\hat{a}$). So possibly this could lead to choosing a different way to select the optimum (e.g. some correction for bias of the estimator).
• At the same time the example shows that it might not matter that much. Even when we make the model with only a few points or with a lot of noise, the result turns out to be quite well. (But, this may not be the case for some more complex model, especially when there is asymptotic and non-linear behavior or non-symmetric cost functions.)

set.seed(1)
layout(matrix(1:3,3)) 

simulate_A <- function() {
  # model
  x <- c(1,3,7,9)
  y <- (1/3) * x^3 -  5^2 * x + rnorm(4,0,100)
  #plot(x,y)
  # fitting
  mod <- lm((y-x^3/3)~0+x)
  # outcome 
  return((-mod$coefficients)^0.5)
}

sample_dist <- replicate(10^5, simulate_A())
hist(sample_dist, main = "histogram of a^0.5", breaks = seq(0,20,1/10), xlim = c(0,10))
hist(sample_dist^2, main = "histogram of a", breaks = seq(0,150,1/2), xlim = c(0,50))
hist(sample_dist^3, main = "histogram of a^1.5", breaks = seq(0,1350,5/2), xlim = c(0,250))

Answer 2

I finally found an answer to this in my class notes. The objective function in a linear program can be derived from other analytic models, which includes linear regression, as long as you can identify constraints to demarcate the feasible solution space.

Note that, it seems that everyone who tried to answer this question got it confused with a related, but more frequently cited problem: using the linear program to optimize the regression (where the coefficients in the regression are what you solve). I'm suggesting reversing that process, solving the regression, then using it as an input in the linear program (so we're solving for the variables).

Answer 3

I believe that in the case of linear programming the quantity you are min/maximising is linearly linked with your parameters (decision variables). In linear regression, you are looking for the vector $\beta$ that minimises the squared error: $y^Ty-2\beta^TX^Ty+\beta^TX^TX\beta$ (obviously $\beta$ is not linearly related to it).

Moreover, in case of linear programming you have constraints, whereas in simple linear regression you do not. However, maybe if you consider the relationships between the variables you want to analyse and the relevant constraints, you could add some penalties to the above function, which will restrict the parameters from going to the area of unfeasible solutions. Nevertheless, still this will not be an equivalent to linear programming, but could be useful for what you want to do.

Answer 4

Least squares regression doesn't have a linear objective function, as the name suggests. However, Linear Programming is the standard way to solve Least Absolute Deviation, or more generally, quantile regression problems. The difference is that least squares gives you a forecast of the conditional mean of the response variable, given the data, while LAD/quantile regression gives you a forecast of the conditional median/quantiles. So if your model is $y = Xb + u$, and you want to find $b$ to minimize the objective:

$\min \sum |Xb - y| $

then you can achieve this by solving the following linear program:

$\min \sum u^+ + u^-$

subject to $y = Xb + u^+ - u^-$ and $u^+, u^- \ge 0$ (so $u^+$ and $u^-$ can be thought of as the positive and negative components of the residuals, respectively)

This is the LAD estimator, its solution, $\hat{b}$, gives a forecast $\hat{y} = X\hat{b}$ of the conditional median of $y$ given $X$. This can be extended to forecasts of arbitrary quantiles. Note that the solution for $\hat{b}$ isn't necessarily unique (fun exercise: when does that happen?), and it's convential to use the lowest value in that case.

Historically, the first examples of regression problems were actually closer to this approach than the now quasi-standard least squares, its modern treatment is largely due to Roger Koenker (here's a great resource if you're interested).

Answer 5

Firstly, great question in terms of linear regression versus linear programming within an optimization context - but I'm still unsure of how you are proposing to use linear regression to derive the objective function:

• Linear regression requires a Y-value and, in this instance, the
  Y-value is the result of the objective function so this wouldn't work as step 1 of an optimization process. Unless I've missed something of course...

• Simulation of a demarcated solution space is simple enough in terms
  of randomly generating (bounded) independent values according to
  relevant distributions. But, you don't need linear regression to
  do this. You do however need an objective function to
  generate the corresponding Y-values.

• Furthermore, to play devil's advocate, once you've generated such a
  bounded solution space you don't need linear programming to find the optimal solution to minimize/maximise the objective function -
  sorting the solution space will suffice.

To-date, I've found linear regression (and decision trees, etc) to be useful - after simulation of the solution space - in cross-checking the coefficients/feature importance in more complicated models.

And of course, linear programming has some impressive algebra to expedite finding the optimal point(s) of a constrained solution space in the first place.

I hope this helps...