# Membership problem for convex cones

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$?

-

## migrated from cstheory.stackexchange.comAug 19 '11 at 6:46

This question came from our site for theoretical computer scientists and researchers in related fields.

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.