2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ So each data point would consist of value for Qh, k, and A. The k, A columns are the predictors, and the Qh would be the response. We could obtain multiple data points from a series of time-consuming, mechanistic simulations. From there we build a regression that predicts Qh from inputs k, A. Then, in our linear program, we would define the objective as finding the: min(10 + (20 * k) + (30 * A)). So now we have a quick regression model that can be used as a 'surrogate model' of our deterministic simulation, to find an optimal combinations of k, A. $\endgroup$ – saeranv Jul 10 '20 at 2:05
  • $\begingroup$ Note that I forgot to add the min/max function to the objective function in the original post, so it was confusingly not really optimizing anything. Fixed it now. $\endgroup$ – saeranv Jul 10 '20 at 2:06
  • $\begingroup$ @SextusEmpiricus, yes your assumptions are all correct, and critique of the problem formulation valid. I've updated the original post to show a more complex optimization problem that shouldn't result in a trivial solution. The basic idea now is that we're trying to minimize the mechanical heating of a room, and increasing one of the variables (Area of glass) acts to both increase heat loss through the wall (which increases mech heating) and increase solar radiation (which reduces mech heating). Still a simple problem, but there's no trivial solution where you can set all variables to just 0. $\endgroup$ – saeranv Jul 10 '20 at 8:29
  • 1
    $\begingroup$ By the way, your new problem is still relatively simple, the optimum is either all glass or all concrete, depending on whether b3<b4 or b3>b4. So do you have a situation where b3 ≈ b4 and you wish to describe the probability/rate of choosing the wrong option? Or you wish to make some other statistical model related to the final solution/outcome of the linear programming problem? (e.g. some Bayesian posterior probability for the probability that glass or concrete is the better choice). The objective function also doesn't seem to make sense to me. Is this your real problem? $\endgroup$ – Sextus Empiricus Jul 10 '20 at 9:08
1
+50
$\begingroup$

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.)

example

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))
$\endgroup$
7
  • $\begingroup$ Thank you for your detailed response. I'm marking this as the right answer (and gave you the bounty) because it has the clearest discussion of the problem (clearer then mine) and some of the problems inherent to it, however I would still appreciate some further clarification on your comment before I fully understand your reasoning. Specifically, what do you mean by: "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..." I'm confused by the No and then Yes. Are both true? $\endgroup$ – saeranv Jul 11 '20 at 5:47
  • $\begingroup$ Re: "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." I haven't been thinking of my problem this way, but I think this is correct, (if I'm understanding you correctly). If I have many parameters with some variance in my objective function, I want to use the linear model to explore the feasible solution space of the problem, and minimize it's expectation. $\endgroup$ – saeranv Jul 11 '20 at 5:55
  • 1
    $\begingroup$ @saeranv It is 'yes and no' because, on the one hand it can matter when you ignore error propagation and do it as two steps instead of a combined method, but on the other hand it may only be a minor offence. In your example, with a trivial solution that is not much influenced by the regression error it doesn't matter. In my example it matters, but only a little but (I could not really come up with an extreme example that is also clear). $\endgroup$ – Sextus Empiricus Jul 11 '20 at 6:13
  • $\begingroup$ just to make sure I understand: when you say 'ignore error propagation', are you referring to the uncertainty in the regression model that we are ignoring when we use it in the linear model? $\endgroup$ – saeranv Jul 11 '20 at 6:38
  • 1
    $\begingroup$ @saeranv My answer is just a nuance. The two-stage idea that you proposed is not so bad. The outcome from different methods of optimization are often not so far apart. A simple method will often already be close to the optimal solution, and a more complex method is often doing only some fine-tuning to give a slightly better result. Whether you can get something out of it will depend on the type of model and the type of goal/application that is to be optimized. $\endgroup$ – Sextus Empiricus Jul 11 '20 at 7:59
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for answering, I'm getting a better idea of the context of linear programming/regression from your answer. But I'm not sure I understand why this wouldn't be considered a valid linear program. Once you have solved your linear regression, can't you use your vector B as coefficients for the linear program objective function? And while it's true linear regression traditionally does not have constraints, it's pretty normal to add constraints in optimization that don't exist in the simulation model (in this case the simulation model is the regression). $\endgroup$ – saeranv Jul 6 '20 at 18:33
1
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ If I'm understanding your response correctly, I think this is confusing the use of linear program techniques to find the best linear regression (by optimizing/minimizing the error), with what I'm actually asking. What I'm asking for is the opposite - once you have solved the linear regression, can you use the (solved) coefficients to define the linear program objective function. Basically, I want to use the linear regression as a simulation model (aka surrogate model), and the linear program to find ways to optimize associated variables. $\endgroup$ – saeranv Jul 6 '20 at 18:49
  • $\begingroup$ Note I've updated my question to clarify the distinction. Hopefully that helps! $\endgroup$ – saeranv Jul 6 '20 at 19:03
1
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ I've been looking all day for this post. I'm guessing you can accomplish with Python using Pulp? or some other Linear Optimizer package. I'm in the same situation - I have run the regression, have the coefficients, need to find the optimal value of the variables. Additionally, I need to be able to solve for a fixed value of the dependent variable. If I'm reading this correctly, it seems like this can be done. $\endgroup$ – logisticregress Sep 24 '20 at 2:39
  • $\begingroup$ @logisiticregress I missed this question, but I think there's very clearly a way to use the regression as the objective function, since they both define a linear equation. However I haven't been able to identify a non-trivial solution for the cases where this can be used (that's why I struggled with the example problem in my posts above). $\endgroup$ – saeranv May 20 at 6:50
1
$\begingroup$

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...

$\endgroup$
4
  • $\begingroup$ For point 1, I am thinking of a scenario where, for example, you have a sparse set of inputs/y-labels that you want to develop a model for (our regression equation) and then use that model to explore other combinations of inputs that weren't present in the original sparse dataset. The relationship between our inputs and the y is what we need for linear programming, not the y-value. $\endgroup$ – saeranv May 20 at 6:40
  • $\begingroup$ For point 2: the objective function is the regression equation. For point 3, you may be right... but why isn't this be true for any linear programming problem? Every linear programming problem defines some bounded solution space that relates constrained inputs to some objective function, why can't you just sort the solution space in those cases as well? $\endgroup$ – saeranv May 20 at 6:45
  • 1
    $\begingroup$ OK, I think we're working on the same question/problem here :- why can't we use linear programming to optimise a regression model built on past (but not necessarily all possible) values by exploring a well-bounded solution space that includes best (better?) estimates of possible values based on domain knowledge. If this is in-line with your objective, I'd like to update my post... $\endgroup$ – Peter May 21 at 2:48
  • $\begingroup$ That is a much clearer way to say what I was trying to express. I assumed all my failed efforts to think of a non-trivial problem where the objective function was a regression was a coincidence. I believe @SextusEmpiricus also ended up finding his solution was trivial, but he assumed, like I did that: "'...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.)." It seems you are suggesting there is a reason for this, if so, that would really awesome to find out. $\endgroup$ – saeranv May 21 at 4:28

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.