First, a quick review of topics from the previous class. In convex optimization, our goal is to either find some in a convex set or declare empty. In order to achieve bounded complexity, we assume that, if is nonempty, then a ball of radius and some arbitrary center is a subset of , and a ball of radius and center 0 contains . Recall that the query complexity for the ellipsoid algorithm of .

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 such that such that and access to a separation oracle for , the Ellipsoid algorithm finds a point in at most queries.

*Proof.*

queries to halve the volume of current ellipsoid. We can go from ball to in halvings. So a total query complexity of .

Here, we introduce the centroid cutting plane algorithm. This algorithm starts with a polytope , which is the cube of side length . Then, we iteratively check the centroid of each to see if . If it is, we have found a feasible point, and the algorithm can terminate. If not, we determine a separating plane (recall the concept of a separation oracle) and set .

*Theorem 2.*

The query complexity of the centroid cutting plane algorithm is .

Note that the factor will require the volume of each successive polytope to be reduced by a constant factor.

*Lemma 1.*

For any halfspace containing the centroid of a convex body , .

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 .

*Lemma 2.*

, where contains the centroid of sample points taken from .

Then, so long as , , 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 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.