5
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ How much more efficient would like it to be? $\endgroup$
    – Igor Rivin
    Commented Nov 10, 2011 at 19:00
  • $\begingroup$ 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. $\endgroup$
    – Miroslav Korbelar
    Commented Nov 10, 2011 at 20:08
  • $\begingroup$ Is there any reference for the algorithm described in the question? $\endgroup$
    – Marcelo Pedro
    Commented Jun 18, 2020 at 3:13

3 Answers 3

Reset to default
4
$\begingroup$

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 https://people.inf.ethz.ch/fukudak/polyfaq/node18.html and some further information at other pages on that site.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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... $\endgroup$
    – Dirk
    Commented Nov 11, 2011 at 9:08
  • $\begingroup$ 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. $\endgroup$
    – mikitov
    Commented Nov 11, 2011 at 9:33
  • $\begingroup$ 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)? $\endgroup$
    – Dirk
    Commented Nov 11, 2011 at 10:24
  • $\begingroup$ 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. $\endgroup$
    – mikitov
    Commented Nov 11, 2011 at 10:40
  • $\begingroup$ 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.. $\endgroup$
    – Miroslav Korbelar
    Commented Nov 11, 2011 at 11:39
1
$\begingroup$

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/)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .