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$

migrated from cstheory.stackexchange.com Aug 19 '11 at 6:46

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

3
$\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.