# Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi, I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the following one:

Let $W$ be a subspace of $\mathbb{R}^{n}$ and $(e_1,\dots,e_n)$ be the standard basis of $\mathbb{R}^{n}$. Find all $F\subseteq\{1,\dots,n\}$ such that $W_{F}:=W\cap \left\langle e_{i}|i\in F\right\rangle$ is 1-dimensional and intersects non-trivially the cone of vectors with non-negative entries (let $u_{F}$ be such non-trivial vector). Then our desired set is generated (as a cone) by all such $u_{F}$ 's for appropriate $F$ 's.

Thanks.

-
How much more efficient would like it to be? – Igor Rivin Nov 10 '11 at 19:00
The algorithm above requires to test (generally) $2^n$ cases of $W_{F}$ (or at least till one doesn't meet the 1-dimensional ones). This seems to be quite much to me. That is why I have asked whether there is known some better implementation or a completely different approach. – Miroslav Korbelar Nov 10 '11 at 20:08

## 3 Answers

This is essentially the vertex enumeration problem in convex geometry. Let $A$ be an $n \times m$ matrix whose columns form a basis the vector space $W$. Then the vectors you're looking for are exactly the products $Av$, where $v \in \mathbb R^m$ generates a ray of the polyhedron defined by $Ay \geq 0$. Thus, up to a linear map, this is the problem of converting from an H-representation to a V-representation of the polyhedron. By duality for convex polyhedra, this is the same as enumerating the defining hyperplanes given the vertex set.

I'm not an expert in the algorithms for this problem, but there seems to be a good discussion of the complexity of some algorithms at http://www.ifor.math.ethz.ch/~fukuda/polyfaq/node18.html and some further information at other pages on that site.

-

Projection Algorithms. See

H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), pp. 367–426.

EDIT: From Drik's comments, it is easy make the method iterative so that at each iteration it is included in the orthogonal set the previously obtained vector. At the end you get an orthogonal basis yet in the intersection.

EDIT2: For a more appealing and engineering-like explanation about the projection algorithm, see Theorodiris's talk slides: ewh.ieee.org/sb/tunisia/enis/dl/Theodoridis_AdaptiveKernel_talk.pdf

-
With this method you can easily find some vector in the intersection. But I think the OP asks for an algorithm to describe the whole intersection... – Dirk Nov 11 '11 at 9:08
It is easy to iterate the method so that each time you get a vector, modify the algorithm so that it is also orthogonal to the previously obtained vectors. At the end you get all vectors from the intersection. – mikitov Nov 11 '11 at 9:33
I see. It is clear that you'll succeed in finding all vertices of the intersection by starting with on ONB (or the canonical basis vectors)? – Dirk Nov 11 '11 at 10:24
It should succeed. Indeed, at each iteration you get a new vector orthogonal from the previous and yet in the intersection. I haven't seen any publication regarding to this tough. – mikitov Nov 11 '11 at 10:40
I don't know still how the algorithm in the paper above works (it has 60 pages), but the intersection I am looking for (i.e. the cone) is generated by the "corner" edges which of course don't need to be orthogonal. But maybe I don't understand your comments right.. – Miroslav Korbelar Nov 11 '11 at 11:39

The algorithm you describe is essential best possible complexity-wise as this is a hard problem.

You may wish to try and use 4ti2 (www.4ti2.de) or Polymake (www.polymake.org/)

-