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