1

Say you have the following system of equations:

100x + 200y + 200z = 250

95x + 180y + 190z = 220

85x + 210y + 210z = 240

with additional constraints on each variable given by:

x >= .55

x <= .75

y >= .80

y <= .95

z >= .10

z <= .25

I have used the lpSolveAPI library in R and there is no solution, which may be true. That is fine; I don't dispute that.

What I am looking for is the solution such that the total error is minimized (i.e. the value of the left hand side vs. the right hand side). What are the best values of x, y and z such that the sum of all the errors of each equation is minimized.

How could I structure this in R using lpSolveAPI? The example below has 3 equations with 3 variables but I'd like to solve a more complex example with 50 equations of the same 3 variables. For reference, a similar approach but where there is a solution is here: Solving a feasible system of linear equations using Linear Programming

I have a feeling I need to modify the objective function in some way. Any thoughts?

Jason
  • 21

2 Answers2

1

I would add slack variables $s_i$ to each of your 3 equations in the system. Thus, these variables represent the error for each function. However, we have to be careful about the sign of each slack variable because we want the sum of their magnitudes to be minimized in the objective function. So we want to minimize $\sum |s_i|$. Can you take it from here? There are excellent resources on here about introducing more variables to get rid of the absolute values in the objective function of an LP.

Edit: For example add constraints $$t_{ip} - t_{im} = s_i$$

$$\forall t \geq 0$$

And the objective is minimize $\sum_i t_{ip} + t_{im}$

Mason
  • 631
  • 4
  • 11
  • Thanks for the idea; intuitively it makes sense though I have no idea where to go from here. My aim is to have someone provide a code snippet to solve as my actual problem may have hundreds of these simultaneous equations. Should I ask that on a different exchange? – Jason Mar 22 '20 at 13:07
  • Hi @Mason, what does "ip" and "im" stand for, and the choice for "t" - does that have any meaning? From what I gather, you split one error term into two values, then restrict all 't' to be greater than 0. Thanks for the guidance; it is (after coming back to the problem) now pointing me in the right direction. – Jason Sep 27 '20 at 17:29
  • @Jason the $p$ index represents the positive part of the slack variable and the $m$ index represents the negative (minus) part of the slack variable. The $i$ index represents the slack corresponding to the $i$th constraint. The variable $t$ is a newly defined variable to serve as a decomposition of the slack. Think of it this way, if the slack (error) is negative, then $t_{im} = -s_i$ and $t_{ip}=0$, making $t$ pick up the positive part of the error. This is a common practice when dealing with minimizing the absolute value of errors. There are many resources on the internet for this. – Mason Sep 27 '20 at 17:37
  • thanks for the clarification. Found this online optimization program/tool to test examples. It did the trick: https://online-optimizer.appspot.com/?model=ms:pPlvqxtPMTkGpON8JYTl4NizLc2AGY4U – Jason Sep 27 '20 at 21:29
1

Here is the code/solution using Matlab which penalizes larger errors via squares vs simply the absolute value of the error.

C = [100, 200, 200; 95, 180, 190; 85, 210, 210];

d = [250, 220, 240];

lb = [.55, .80, .10]; ub = [.75, .95, .25];

ABC = lsqlin(C, d,[],[],[],[],lb,ub)

ABC = 3x1 [0.6381, .8000, .1000]

The values that minimize the least squares error for x, y and z are x = .6381, y = .8000, z = .1000

Jason
  • 21