10

My question is:

Are there any criteria to decide whether a system of linear equations allows a solution where all variables are greater than 0?

Clearly, I could compute the solution space and check if there is a solution that satisfies the condition. But is there any better way?

Oliver Witt
  • 201
  • Hm, what about this relaxation: We are looking for an "all non-zero solution". Such a solution exists, if for each variable, there is a solution that is non-zero for this variable. Hence, we are trying to find out whether there is a variable that is zero for all solutions. This is quite a strong property that could possibly be exploited. The "all positive solution" question showed up while doing some research on flow networks. The variables are actually edge capacities and they need to be positive in that context. – Oliver Witt Jan 15 '15 at 18:14

1 Answers1

6

You are asking to solve the linear feasibility problem $Ax=b$ with $x \succ 0$. This is called the "Phase 1" problem in convex optimization because interior point algorithms require a feasible starting point. Without loss of generality, assume the rows of $A$ are scaled so that $b$ is entirely positive. This Phase 1 problem reduces to solving an alternate linear program $Ax+y=b$ with $x+y\succ 0$, where $x=0$ and $y=b$ is a trivial initial solution. Thus determining feasibility requires solving a linear program.

Victor Liu
  • 3,721
  • 2
    The link is broken now. I found a similar article in section 11.4 here: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf – LouYu Jan 18 '22 at 00:45