I have a system of linear equations that I need a solution for that is strictly positive. I have 4 solutions and 4 unknowns, and the solution I obtain for my current system involves negative numbers. For illustrative purposes, here is the system: $$x_1+ x_2 + x_3 + x_4 = 1$$ $$0.2895 x_1+1.2312 x_2 + 0.8360 x_3+ 0.5515 x_4 = 0.665$$ $$0.2942 x_1+ 0.5828 x_2 + 0.4561 x_3 + 0.4006 x_4 =0.47$$ $$7,969,147 x_1 +21,685 x_2+ 2,656,382 x_3 +7,083,686 x_4 = 1,328,191.2$$

I can vary the coefficients in my equations a little bit and I can vary the LHS of two of my equations (a little bit).

I had originally tried to treat this problem as a Linear Programming problem but was unable to find solutions for my given coefficients even while varying the LHS of the equations.

So my question is: How can I go about selecting coefficients from within a certain range without feeling like I am just stabbing in the dark? Is there a name for this type of problem? It would be a Linear Programming problem but I want to be able to vary the coefficients in my constraints until I find a solution and I also don't have an objective function.

Below is the current system I'm considering. All of my coefficients must be positive. I can make adjustments to the coefficients on line 2 by less than 0.5 each. I can change coefficients in line 4 drastically (by millions). I can make no adjustments to coefficients in lines 1 or 3. $$x_1+ x_2 + x_3 + x_4 = 1$$ $$ 0.64 \geq 0.2895 x_1+1.2312 x_2 + 0.8360 x_3+ 0.5515 x_4 \leq 0.67$$ $$0.44 \geq 0.2942 x_1+ 0.5828 x_2 + 0.4561 x_3 + 0.4006 x_4 \leq 0.48$$ $$7,969,147 x_1 +21,685 x_2+ 2,656,382 x_3 +7,083,686 x_4 = 1,328,191.2$$

  • $\begingroup$ While in some sense you "can" do that, the real issue is likely what purpose will be served. Certainly it would improve the Question to add some motivation. Without knowing more I'd be inclined to add nonnegativity constraints and remove some equations until the resulting linear program is feasible. $\endgroup$ – hardmath Aug 12 '19 at 23:50
  • $\begingroup$ Thank you for the response. I don't see the relevance of my motivation :) it's a problem I am facing at work. All four equations are required. The only thing I can do is adjust some of the coefficients. So I guess the motivation I can give is: I need a system of 4 equations that has at least one positive solution; I am able to tweak the some of the coefficients to achieve this. The real issue is: \textit{how} can I find the coefficients that will create a system with a solution. $\endgroup$ – LambdAmy Aug 13 '19 at 15:28

If we simply solve the initial system of four linear equations in four unknowns, its unique solution is this: $$ x_1 = -10.1019 \\ x_2 = -10.3069 \\ x_3 = 15.7201 \\ x_4 = 5.6887 $$

This solutions is not nonnegative (forgive the use of a double negative!), and so is unsatisfactory. There is a natural 3D geometric interpretation of the system, arising from the first equation that the sum of coefficients is one. If all four variables are to have nonnegative values (yet sum to one), then these are barycentric coordinates for the vector formed by the right-hand sides of the last three equations, in terms of the coefficents of the unknowns in the same three equations.

In other words, consider the four corners of a tetrahedron:

$$ P_1 := ( 0.2895, 0.2942, 7969147) \\ P_2 := ( 1.2312, 0.5828, 21685) \\ P_3 := ( 0.8360, 0.4561, 2656382) \\ P_4 := ( 0.5515, 0.4006, 7083686) $$

We were hoping to find that the point $Q := ( 0.665, 0.47, 1328191.2)$ belongs to the convex closure of those four corners. But it doesn't, as the solution of the linear system above tells us.

The issue then becomes whether the "little bit" of variation you are willing to allow will be sufficient to move the target point $Q$ inside the tetrahedron.

To avoid "stabbing in the dark" we can first ask about the distance the target $Q$ is from the closest point to it on the tetrahedron $P_1 P_2 P_3 P_4$. Any adjustments to point coordinates should be made in a way that reduces this distance to zero. What the problem statement permits (if I understand it correctly) is that the $x$ and $z$ coordinates can be adjusted to some extent, but not the $y$ coordinates.

I need to go run an errand, but when I get back I'll do the numeric experiment and tell you if the adjustments allow for that (and explain why or why not).


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.