A randomized cutting plane scheme with geometric convergence: Probabilistic analysis and SDP applications

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. The method is analyzed under the assumption that a Uniform Generating-Oracle (UGO) is available - an algorithm for uniform generation of random points in the convex body. The expected rate of convergence for such method is geometric. Probabilistic estimates of convergence are explicitly derived: we estimate the probability that the method converges slower than the deterministic center-of-gravity algorithm. Since UGO is unavailable in most applications, a practical implementation of the method is discussed, based on Hit-and-Run versions of Markov-chain Monte Carlo algorithms. The crucial notion for this algorithm is a Boundary Oracle, which is available for most optimization problems, including LMIs and many other types of constraints. Numerical results for SDP problems are presented, which confirm that the randomized approach can be a competitor to modern deterministic interior-point algorithms.