2
$\begingroup$

Assume we have the under-determined linear system $$ Ax = y $$ $$A \in \mathbb R^{m \times n}_{\geq 0},\, y \in \mathbb R^m_{\geq 0},\, m < n,$$ for which we know a non-negative solution $x^* \in \mathbb R^n_{\geq 0}$. The problem is to verify that $x^*$ is the unique non-negative solution.

Note. I use $\mathbb R_{\geq 0}$ as a notation for a set of non-negative real numbers. Note that all the parameters of the problem are non-negative.

I know the following (hopefully correct) deterministic algorithm to solve the problem:

  1. Let $I = \{ i | x^*_i \neq 0 \}$ is the support of a vector $x^*$.
  2. Let $A_I$ be a matrix consisting of columns of $A$ with indexes in $I$. If $A_I$ has rank less than number of its columns, there exists for sure another non-negative solution. (Proof omitted. Intuition: we can take some solution of $A_I e = 0$ of small enough norm, then $(x^* + e)$ is another non-negative solution of original system).
  3. Otherwise consider the following linear programming problem: $$ dx \rightarrow \max $$ $$ \text{s.t. } Ax = y, x \geq 0 $$ where $d = (d_i) \in \mathbb R^n$ is defined as follows: $$ d_i = \begin{cases} 1, \text{ if } x^*_i = 0, \\ 0, \text{ otherwise}. \end{cases} $$
  4. The original system has unique non-negative solution if and only if the aforementioned linear programming problem outputs $x^*$ as its solution. (Intuition: if solving LPP gives us the same $x^*$, then all the non-negative solutions of $Ax=y$ have zeros at positions $\{1,2,\dots,n\} \setminus I$. Then step 2 guarantees the uniqueness).

However, I want to have a more efficient algorithm as I need to verify plenty of such systems with a fixed matrix $A$ of size $n \approx 300$ for different pairs $(x^*,y)$ where $y=Ax^*$.

I did not find faster deterministic algorithm so I decided to check out randomized algorithms hoping that this can reduce complexity. Does anyone know an algorithm to solve the original problem that is

  • Las Vegas? I.e. an algorithm that uses randomness but gives solution that is always correct.
  • Monte Carlo? I.e. an algorithm that gives a wrong answer with small probability. I will then run it couple of times to make error probability small enough.

P.S. I am aware about questions here and here. However they do not explicitly speak about randomized algorithms.

$\endgroup$
7
  • $\begingroup$ If the system is underdetermined, then the null space of $\rm A$ is nontrivial. Using SVD, we can find a basis for the null space. Adding this null space to $\rm x^*$, we obtain an affine space. Lastly, we can do a random walk on this affine space until we find another nonnegative solution or we quit, whichever comes first. $\endgroup$ Dec 12, 2016 at 17:46
  • $\begingroup$ Can you elaborate on probability of success and details of this walk? $\endgroup$ Dec 12, 2016 at 21:30
  • $\begingroup$ Is $\rm x^*$ a basic feasible solution? If so, one has $m$ choices on which variable to leave the basis and $n-m$ choices on which to enter the basis. In total, $m (n-m)$ choices. One could sample from this set of choices. Each choice would produce a linear system to solve. We only need to find one linear system whose solution is nonnegative. $\endgroup$ Dec 12, 2016 at 22:14
  • $\begingroup$ No, $x^*$ is not a basic feasible solution (in simplex algorithm terminology). Well, to be precise we are not guaranteed that. $\endgroup$ Dec 13, 2016 at 9:07
  • $\begingroup$ This looks like a total complementarity problem. $\endgroup$
    – Surb
    Jun 6, 2017 at 16:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.