7
$\begingroup$

Inspired by the question, I would like to ask the following question:

Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection $f(\Theta)= \{(\vec{c}_1\cdot \vec{x}+ d_1, \cdots, \vec{c}_m\cdot \vec{x}+d_m)\mid A\vec{x}\leq b\}$, a point $\vec{y}\in \mathbf{Q}^m$

Decide whether $\vec{y}$ is a vertex of $f(\Theta)$, what's the complexity?

I strongly believe there is a polynomial time (one might obtain many $\vec{x}$'s which project to the given $\vec{y}$ and check one of these $\vec{x}$'s is a vertex of $\Theta$?). However, I do not have a clear algorithm.

$\endgroup$
  • $\begingroup$ I assume that $d_1,\dots,d_m$are supposed to be scalars (otherwise $c_i\cdot x + d_i$ makes no sense), i.e. you have $f(\Theta) = C\Theta + d$ for a matrix $C$ and vector $d$. Do you assume $C$ to have full row rank? Otherwise not all vertices of $\Theta$ will be mapped to vertices of $f(\Theta)$. $\endgroup$ – Klaus Draeger Oct 7 '15 at 10:19
  • $\begingroup$ Yes, you are right; I will correct them; I do not assume $C$ to be full row ranked. $\endgroup$ – maomao Oct 7 '15 at 10:33
  • 5
    $\begingroup$ Given a polytope $P$ and a point $x$ one can write $x$ as a convex combination of vertices of $P$ in polynomial time iff one can optimize or separate over $P$. This should help address your problem, I think. $\endgroup$ – Chandra Chekuri Oct 7 '15 at 12:59
  • $\begingroup$ Unfortunately $P$ can have exponentially many vertices, so I don't think that approach provides a polynomial-time algorithm in general. $\endgroup$ – D.W. Apr 14 '17 at 17:06
  • 3
    $\begingroup$ @D.W. Are you referring to Chandra's comment? It doesn't matter how many vertices $P$ has: any point in $P$ can be written as the convex combindation of at most $m + 1$ vertices, by Caratheodory's theorem. And such a convex combination can be found in polynomial time using a separation oracle for $P$, which can be constructed from a separation oracle for $\Theta$. (See e.g. page 185 of Schrijver's Integer and Linear Programming.) Since a point $y$ in $P$ is extremal (i.e. cannot be written as the convex combination of other vertices) if and only if it is a vertex, this solves the problem. $\endgroup$ – Sasho Nikolov Apr 15 '17 at 11:37
5
$\begingroup$

This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ could be given by a separation oracle, rather than explicitly, and it is also possible to solve an appropriately formulated version for a polyhedron.

Observe first that we have an efficient separation oracle for $P = f(\Theta) = C\Theta + d$. Indeed, deciding $y \in P$ amounts to solving the feasibility problem $$ y = Cx\\ Ax \le b $$ over the variables $x$. This problem can be solved with the usual techniques, e.g. the ellipsoid method. By the equivalence of separation and optimization, we can also solve arbitrary linear optimization problems over $P$.

Let us first assume $y \in P$: otherwise we are done. Then, by Caratheodory's theorem, $y$ can be written as a convex combination of at most $m+1$ vertices of $P$. Moreover, such a convex combination is computable in polynomial time using a separation/optimization oracle for $P$: this is proved, for example, in Corollary 14.1g of Schrijver's Theory of Linear and Integer Programming. I.e., given an efficient separation oracle for $P$, we can construct a procedure that takes $y$ and returns vertices $v_1, \ldots, v_k$ of $P$, $k \le m+1$, and coefficients, $\lambda_1, \ldots, \lambda_k \in (0,1]$ such that $y = \sum_{i = 1}^k{\lambda_i v_i}$. Then, $y$ is a vertex of $P$ if and only if the procedure returns $v_1 = y$ and $\lambda_1 = 1$. It is clear that if this happens, $y$ is a vertex. Conversely, if this does not happen, then $y$ can be written as a convex combination of other points in $P$, which means that $y$ is not extremal, and, therefore, not a vertex.

Computing $v_1, \ldots, v_k$ and $\lambda_1, \ldots, \lambda_k$ using a separation/optimization oracle is not too hard. First you compute a vertex $u_1$ of $P$: figuring out how to do this by optimizing over $P$ is a nice exercise. If $u_1 = y$, we are done. Otherwise, let $\ell$ be the half-line starting at $u_1$ and going through $y$, and let $z$ be the point where $\ell$ intersects the boundary of $P$. Then $z$ lies in a proper face of $P$, and we can recurse on that face to express $z$ as a convex combination of the vertices of the face. We finish by expressing $y$ as a convex combination of $z$ and $u_1$. See Schrijver's book for the details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.