<p>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.</p>

<p>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$.</p>

CC BY-SA 3.0
2012-07-26T11:39:16.500Z
Thanks! I added an assumption that the polytope is rational, so (hopefully) now, there is hope of finding a point in P.
Guy
CC BY-SA 3.0
2012-07-27T03:05:53.097Z
That restriction doesn't help; it's easy to make $\hat{P}$ rational in David's construction.
Jeffε
CC BY-SA 3.0
2012-07-28T00:56:36.773Z
I am guessing the questioner is really asking how to find a point $p \in P$ when $P$ is not full dimensional.
Chandra Chekuri
CC BY-SA 3.0
2012-07-24T23:08:30.183Z
2012-07-24T23:08:30.183Z
David Eppstein
<p>If your goal is to find a point in $P$ or determine that $P$ is empty, why don't you do the following.</p>

<p>Let $H$ be a set of half-spaces, initially empty.</p>

<p>Let $x$ be a point, initially equal to $0^k$.</p>

<ol>
<li><p>Give $x$ to the oracle.</p></li>
<li><p>If the oracle said $x \in P$, you've done.</p></li>
<li><p>Otherwise, let $S$ be the violated half-space returned by the oracle. Let $y$ be the orthogonal projection of $x$ on $S$.  </p>

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

CC BY-SA 3.0
2012-07-26T17:30:41.800Z
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
CC BY-SA 3.0
2012-07-26T18:19:32.390Z
You are welcome! Are you sure that such requirement about the running time is evident by reading the question?
Giorgio Camerani
CC BY-SA 3.0
2012-07-26T18:26:40.537Z
You're right. I'll add it.
Guy
CC BY-SA 3.0
2012-07-26T17:05:24.877Z
2012-07-27T08:54:28.790Z
2012-07-27T08:54:28.790Z
Giorgio Camerani
<p>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$. </p>

<p>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.</p>

<p>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. </p>

<p>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$?</p>

<ds.algorithms><convex-optimization><convex-geometry><high-dimensional-geometry>
Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$
Guy
# Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$

(Asked by: username_0 on 2012-07-24)

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$?

**Tags:** ds.algorithms, convex-optimization, convex-geometry, high-dimensional-geometry

---

## 2 answers

### Answer by username_1 on 2012-07-24. Score: 8 | Accepted answer

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$.

> **Comments:**
> **username_0**: Thanks! I added an assumption that the polytope is rational, so (hopefully) now, there is hope of finding a point in P.  
> **username_2**: That restriction doesn't help; it's easy to make $\hat{P}$ rational in David's construction.  
> **username_3**: I am guessing the questioner is really asking how to find a point $p \in P$ when $P$ is not full dimensional.  

---

### Answer by username_4 on 2012-07-26. Score: 2

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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: You are welcome! Are you sure that such requirement about the running time is evident by reading the question?  
> **username_0**: You're right. I'll add it.  

---

