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.

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.