0
$\begingroup$

Given a set of vectors $S=\{v_1, v_2,...,v_d\} \subset \mathbb{R}^{N}, \, N>d$, is there any algorithm to decide if there exist a vector with all coordinates strictly positive in the generating subspace $\langle S \rangle$?
I am aware of results like Farka's Lemma (or variants as Gordon's Theorem, etc...). Or some papers like: Ben-Israel, Adi. "Notes on linear inequalities, I: The intersection of the nonnegative orthant with complementary orthogonal subspaces." Journal of Mathematical Analysis and Applications 9.2 (1964): 303-314.
But I am looking for an algorithm to decide yes or no.

$\endgroup$
1
$\begingroup$

Let $$M = \begin{pmatrix} | & | & \cdots & | \\ v_1 & v_2 & \cdots & v_d \\ | & | & \cdots & | \end{pmatrix}$$ and let $e_1, \ldots, e_N$ be the standard unit vectors. Then consider the linear programs indexed by $i = 1, \ldots, N$:

$$\begin{aligned} &\text{maximize }\langle e_i,Mx\rangle \\ &\text{subject to }\langle e_j, Mx\rangle \ge 0,\quad j=1,\ldots,N \end{aligned}$$

Clearly if any of these programs is unsatisfiable, then all of them are, and moreover $\langle S\rangle$ is disjoint from the positive orthant. So assume all programs are satisfiable.

If the $i$th program is bounded, let $x^{(i)}$ be its optimal solution and $y^{(i)}$ be its optimal value. If it is unbounded, add the constraint $\langle e_i, Mx\rangle \le 1$, and let $x^{(i)}$ be the optimal solution to this modified program, and the optimal value becomes $y^{(i)} = 1$.

If any of the $y^{(i)}$ are zero, then clearly $\langle S\rangle$ is disjoint from the positive orthant.

In the remaining case, where the programs are satisfiable and all optimal values are positive, let $x^{(i)}$ be the optimal solution for the $i$th program and let $y^{(i)}$ be the optimal value for the $i$th program. Since $\langle e_i, Mx^{(i)}\rangle = y^{(i)} > 0$ and $\langle e_j, Mx^{(i)}\rangle \ge 0$, all by construction, we can take any linear combination $\sum a_i Mx^{(i)}$, with all $a_i > 0$, to obtain a point in the intersection of $\langle S\rangle$ with the positive orthant.

In summary, if all the programs are satisfiable and have positive optimal values, then yes; otherwise, no. Note that adding constraints to make all programs bounded is for convenience of proving correctness, but unimportant for implementing the algorithm (one needs only check that all optimal values are either positive or infinite).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ srossd, can you point out any reference about the algorithm that you described? Or even, any reference that you think can help me? Thanks. $\endgroup$ – Marcelo Pedro Jun 18 at 2:56
  • 1
    $\begingroup$ I don't have any references for this algorithm in particular. It's a direct application of LP, though. Each program asks the question "does this subspace intersect the positive $e_i$ half-space?". If each answer is yes, then by linearity, the subspace intersects the positive orthant. Otherwise, no. $\endgroup$ – srossd Jun 18 at 19:18
  • 1
    $\begingroup$ Here's a quick python implementation, if that helps. repl.it/@srossd/IntersectsPositiveOrthant $\endgroup$ – srossd Jun 18 at 19:31

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.