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$
6
  • $\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$ Oct 7, 2015 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, 2015 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$ Oct 7, 2015 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, 2017 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$ Apr 15, 2017 at 11:37

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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