1
$\begingroup$

Suppose I have a set of vectors $\{\mathbf s_1, \dots, \mathbf s_N\} \subset \mathbb Z^n$, and I want to find all conic combinations that give the zero vector. In other words, I want to find all vectors $\mathbf x \in \mathbb R^N$ such that $\mathbf x \geq \mathbf 0$ and

\begin{equation} \sum_{i=1}^N x_i \mathbf s_i = \mathbf 0. \end{equation}

Is there an algorithm for solving this problem?

Update: I was a little imprecise in saying that I wanted to find "all vectors...". To clarify, the set of $\mathbf x$ vectors that satisfy $\mathbf x \geq \mathbf 0$ and \begin{equation} \sum_{i=1}^N x_i \mathbf s_i = \mathbf 0. \end{equation} is a cone. I want to find the extreme rays of this cone.

$\endgroup$
1
$\begingroup$

In general, enumerating the extreme points or extreme rays of a polytope is a hard problem. If the size of the problem were not too large, and I had to write my own code to do it, I'd probably do something along the lines of:

  1. Add the constraint $x_1 + \dots + x_N = 1$, which turns conic into convex combinations and (relevantly) turns all extreme rays into extreme points.
  2. Use phase 1 of the simplex method to find one vertex.
  3. Explore all the other extreme points by a standard breadth-first or depth-first search, trying all possible pivoting steps to go from a vertex to its adjacent vertices.

But there's also existing software that solves the problem for you, e.g. lrs which is just the first one I found on Google. Your task is exactly converting an H-representation of the polytope (the $2n+N$ linear inequalities that $\mathbf x$ must satisfy) into a V-representation (the extreme points and extreme rays).

$\endgroup$
0
$\begingroup$

Ordinary Gaussian elimination will give you a parametric equation for the subspace of all $x$s that satisfy your equation. The requirement that $\mathbf x\ge 0$ now easily translates to $N$ simultaneous linear inequalities in the parameter space.

Arguably those $N$ simultaneous linear inequalities is the best you can hope for to "find all vectors" -- in that such a system of linear inequalities is the standard way to describe a convex polytope in $\mathbb R^k$ in in the first place, such as when giving input to a linear programming solver.

If the parameter space is $2$- or perhaps $3$-dimensional you can probably understand the solution space "by eye". For higher dimensions it may not be clear whether there are solutions at all; a practical approach could be to feed all the inequalities to an off-the-shelf linear programming solver and ask it to minimize, say, $x_1$.

$\endgroup$
  • $\begingroup$ I agree that there could easily be infinitely many solutions. In fact, it's straightforward to show that the set of solutions is a cone. So I suppose what I am really after is the extreme rays of this cone. I will update the question accordingly. $\endgroup$ – Garrett Aug 23 '18 at 21:47

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.