Cutting Plane Method

First, a quick review of topics from the previous class. In convex optimization, our goal is to either find some $x$ in a convex set $K$ or declare $K$ empty. In order to achieve bounded complexity, we assume that, if $K$ is nonempty, then a ball of radius $r$ and some arbitrary center is a subset of $K$ , and a ball of radius $R$ and center 0 contains $K$ . Recall that the query complexity for the ellipsoid algorithm of $O(n^2 \log \frac{R}{r})$ .

Each iteration of Ellipsoid algorithm only needs a violated inequality for the current query point. This is done by a separation oracle. It does not need any other access to the feasible set!

Theorem 1.
Given $r, R$ such that $\exists x_0$ such that $x_0 + rB_n \subseteq K \subseteq RB_n$ and access to a separation oracle for $K$ , the Ellipsoid algorithm finds a point $x \in K$ in at most $O(n^2 \log\frac{R}{r})$ queries.

Proof.
$O(n)$ queries to halve the volume of current ellipsoid. We can go from ball $R^n$ to $r^n$ in $n \log\frac{R}{r}$ halvings. So a total query complexity of $O(n^2 \log\frac{R}{r})$ . $\square$

Here, we introduce the centroid cutting plane algorithm. This algorithm starts with a polytope $P_0$ , which is the cube of side length $R$ . Then, we iteratively check the centroid $z$ of each $P_i$ to see if $z \in K$ . If it is, we have found a feasible point, and the algorithm can terminate. If not, we determine a separating plane $a^Tx \leq a^Tz$ (recall the concept of a separation oracle) and set $P_{i+1} = P_i \cap \{x : a^Tx \leq a^Tz\}$ .

Theorem 2.
The query complexity of the centroid cutting plane algorithm is $O(n \log \frac{R}{r})$ .

Note that the $\log \frac{R}{r}$ factor will require the volume of each successive polytope to be reduced by a constant factor.

Lemma 1.
For any halfspace $H$ containing the centroid of a convex body $K$ , $vol(K \cap H) \geq \frac{1}{e} vol(K)$ .

We will not do the proof in class, but the two-dimensional case is a HW problem.

Unfortunately, the centroid cutting plane algorithm has a major problem: computing the centroid is #P-Hard (informally, worse than NP-Hard). To get around this issue, we will calculate an approximate centroid instead, by taking the average of random points in $K$ .

Lemma 2.
$E[vol(K \cap H)] \geq \left(\frac{1}{e} - \sqrt{ \frac{n}{m} }\right) vol(K)$ , where $H$ contains the centroid of $m$ sample points taken from $K$ .

Then, so long as $m > ne^2$ , $\left(\frac{1}{e} - \sqrt{\frac{n}{m}}\right) > 0$ , and each successive polytope is still reduced by a constant factor (although a smaller one, but this is irrelevant).

Now, we need to figure out how to randomly sample from a polytope. First, we recall the idea of a membership oracle, which is weaker than a separation oracle, but only returns whether or not a given point is in a set (no separating hyperplane is ever returned). Then, consider the following algorithm for finding a random point in a convex set: start with any point in the set. Iteratively draw a chord across the set in a direction chosen uniformly at random. Then, choose a point uniformly at random from this chord, and update the point to the newly chosen point.

Under further assumptions, this process will find a point chosen uniformly at random from the convex set after $O(n^3)$ iterations. We do not prove this fact in class. Note that this entire procedure is only used to find a single random sample, and needs to be repeated in its entirety in order to find a second random sample.

Share this:

Like this: