4
$\begingroup$

Does anyone have a reference for the most efficient or some simple reasonably efficient algorithm for the membership problem for convex cones:

Given a finite set of vectors $v_1, ..., v_n$ and a vector $v$, how do you determine whether $v=p_1 v_1+\cdots+p_nv_n$ for some collection of positive numbers $p_k$?

$\endgroup$
4
$\begingroup$

Suppose that the vectors $v_1, ..., v_n$ are $m$-dimensional. Build an $m \times n$ matrix $A$ such that the vectors $v_i$ are columns of $A$. The problem is now formulated as follows. Find the $n$-dimensional vector $x = (p_1, ..., p_n)^T$ such that: $$ Ax = v \;\;\mbox{(Eq. 1)}$$ $$ x \ge 0 \;\;\; \mbox{(component-wise) (Eq.2)} $$

Let us assume that $\operatorname{rank} (A) = m$. If $m \gt n$ then there is no solution. If $m = n$ then we can solve (Eq. 1) and check whether the unique solution satisfies (Eq. 2). The only interesting case is hence $m \lt n$. Since any positive values of $x_i = p_i$ are accepted as a solution we can as well search for values that minimize

$$g(x) = x_1 + ... + x_n \;\;\; \mbox{(Eg. 3)}$$

We have now a linear programming problem: Minimize the linear goal function (Eq. 3) under the $m+n$ linear constraints (Eq. 1-2). This can be solved efficiently by the simplex algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy