Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

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.

add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.