A Randomized Cutting Plane Method with Probabilistic Geometric Convergence

We propose a randomized method for general convex optimization problems; namely, the minimization of a linear function over a convex body. The idea is to generate N random points inside the body, choose the best one and cut the part of the body defined by the linear constraint. We first analyze the convergence properties of … Read more