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.

Improve this question
$\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$
    – Rodrigo de Azevedo
    Commented Dec 12, 2016 at 17:46
  • $\begingroup$ Can you elaborate on probability of success and details of this walk? $\endgroup$
    – Yauhen Yakimenka
    Commented 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$
    – Rodrigo de Azevedo
    Commented 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$
    – Yauhen Yakimenka
    Commented Dec 13, 2016 at 9:07
  • $\begingroup$ This looks like a total complementarity problem. $\endgroup$
    – Surb
    Commented Jun 6, 2017 at 16:15

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .