1
$\begingroup$

I have a question that might or might not be trivial for experts from the linear programming world.

We have a system of linear equations that we want to solve: $A\cdot x=0$, with the constraint that all variables are non-negative: $x_i \geq 0 ~\forall i$.

The system is underdetermined, i.e. $A$ has more columns than rows, more variables than equations.

Question: How do we determine which $x_i$ can never be positive (i.e. are zero) in the solution space. That means, determine those $x_i$ for which $ x_i = 0$ for any solution.

Thanks!

$\endgroup$
  • $\begingroup$ In theory you could enumerate all basic feasible solutions and check. $\endgroup$ – Erwin Kalvelagen Jun 11 '18 at 20:04
1
$\begingroup$

Hint

Since $A$ is a $m \times n$ matrix, with $m<n$, a Singular Values Decomposition of it will represent a first useful step.

In particular you can determine the null-space of it, i.e. the set of vectors $v_1, v_2, \cdots, v_{n-m}$ (or more) for which $$ {\bf A}\,{\bf v}_{\,k} = {\bf 0}\quad \Rightarrow \quad {\bf A}\,\sum\limits_k {\lambda _{\,k} } {\bf v}_{\,k} = {\bf 0} $$ and thereby reduce your problem to a $m \times m$ system.

$\endgroup$
0
$\begingroup$

If the $i^{th}$ column has at least one non-zero component that is of the same sign as every other component in the same row, then $x_i$ must be equal to $0$. This can be iterated, by setting to $0$ any $x_i$ that "passes" the test, removing the corresponding column from $A$, and repeating the test until it "evicts" no more columns.

But this is only a sufficient condition, not necessary (i.e. if it is true, then $x_i$ must be $0$; but $x_i$ could be $0$ for other reasons). Frankly, I do not know if there is a "simple" necessary and sufficient condition.

$\endgroup$
0
$\begingroup$

If the problem is an actual numerical problem for which you have a matrix A, then you can set this problem up as a semidefinite program (see Convex Optimization by Boyd and Vandenberghe).

Such a system can be solved by good convex solvers like cvx, or sedumi and yalmip in Matlab, or Pyopt in python. In this case, since $I$ is the only inequality, this is a simple linear program.

In your case, $$ \begin{align} & \underset{x}{\text{minimize}} & & 1^T x \\ & \text{subject to} & & -I_{n,m}x \le 0 \\ & & & Ax = 0 \end{align} $$

This should provide a minimally non-negative answer for $x$ based on the constraints.

$\endgroup$

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.