# Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$

Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but since $m$ is very large, we use an oracle, that given a point $x \in R^k$, either says $x \in P$ or returns a half-space such that $x \notin S$.

My goal is to find a point in $P$ or determine that $P$ is empty. I'm aiming for a polynomial running time in the representation size of $U$ and $k$, where $U$ is the largest absolute value in $A$. That is, the algorithm should make only polynomial many calls to the separation oracle.

In general, $P$ might be contained in a hyper-plane of lower dimension and thus it is problematic to use the ellipsoid method. So, as in Khachiyan's trick, I alter $P$ (and the separation oracle) to use $P^\epsilon$, where $\epsilon$ is something like $1/U$. Intuitively, the half-spaces that define $P^\epsilon$ are the same as the ones that define $P$ only that they are translated by $\epsilon$. The polytope $P^\epsilon$ has the following properties: $P^\epsilon$ is empty iff $P$ is empty, and if $P$ is not empty, $P^\epsilon$ is full-dimensional.

My question is as follows: Assume the algorithm finds a point $p \in P^\epsilon$. Is it possible to generate a point in $P$ using $p$?

## 2 Answers

From any choice of a polytope $P$ in ${\mathbb R}^k$, $\epsilon$, and a point $q$ in ${\mathbb R}^k$ it is possible to find a polytope $\hat P$ in ${\mathbb R}^{k+1}$, together with an embedding of ${\mathbb R}^k$ into ${\mathbb R}^{k+1}$, such that $\hat P$ is within $\epsilon$ Hausdorff distance of (the embedded image of) $P$ and such that (the embedded image of) $q$ belongs to $\hat P^\epsilon$. To do this, simply make the facets of $\hat P$ be nearly parallel to the embedded image of ${\mathbb R}^k$, so that translating them by $\epsilon$ in ${\mathbb R}^{k+1}$ causes their intersection with ${\mathbb R}^k$ to move away from $\hat P$ by a much greater distance.

Because $q$ was arbitrary, the knowledge of $q$ is of no use in finding a point in or near $P$; everything you could do with it you could do without it. But, because $\hat P$ and $P$ are so close, finding a point near $P$ is equivalent to finding a point near $\hat P$. Therefore, the knowledge of $q$ (a point in $\hat P^\epsilon$) is of no use in finding a point near $\hat P$.

• Thanks! I added an assumption that the polytope is rational, so (hopefully) now, there is hope of finding a point in P. – Guy Jul 26 '12 at 11:39
• That restriction doesn't help; it's easy to make $\hat{P}$ rational in David's construction. – Jeffε Jul 27 '12 at 3:05
• I am guessing the questioner is really asking how to find a point $p \in P$ when $P$ is not full dimensional. – Chandra Chekuri Jul 28 '12 at 0:56

If your goal is to find a point in $P$ or determine that $P$ is empty, why don't you do the following.

Let $H$ be a set of half-spaces, initially empty.

Let $x$ be a point, initially equal to $0^k$.

1. Give $x$ to the oracle.

2. If the oracle said $x \in P$, you've done.

3. Otherwise, let $S$ be the violated half-space returned by the oracle. Let $y$ be the orthogonal projection of $x$ on $S$.

• If there exists at least one $T \in H$ such that $y \not \in T$, then you've done: $P$ is empty.
• Otherwise set $H := H \cup \{S\}$, and set $x := y$.
4. Go back to 1.

• Thanks for the response. I think it will work, but, unless I'm missing something, the running time will be porportional to $m$, the number of half-spaces that define $P$. I'm hoping for a running time that is polynomial in $k$ and the representation of $U$, which is the absolute largest value in $A$. That is, only polynomial many calls to the oracle. – Guy Jul 26 '12 at 17:30
• You are welcome! Are you sure that such requirement about the running time is evident by reading the question? – Giorgio Camerani Jul 26 '12 at 18:19
• You're right. I'll add it. – Guy Jul 26 '12 at 18:26