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