  


A Randomized Cutting Plane Method with Probabilistic Geometric Convergence
Fabrizio Dabbene(fabrizio.dabbenepolito.it) Abstract: 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 the algorithm from a theoretical viewpoint, i.e., under a rather classical assumption that an algorithm for uniform generation of random points in the convex body is available. Under this assumption, the expected rate of convergence for such method is proved to be geometric. Moreover, explicit sample size results on convergence are derived. In particular, we compute the minimum number of random points that should be generated at each step in order to guarantee that, in a probabilistic sense, the method converges at least as fast as the deterministic centerofgravity algorithm. From a practical viewpoint, the method can be implemented using HitandRun versions of Markovchain Monte Carlo algorithms, and we show how these convergence results can be extended to a HitandRun implementation. A crucial notion for the HitandRun implementation is that of Boundary Oracle, which is available for most optimization problems including LMIs and many other kinds of constraints. Preliminary numerical results for SDP problems are presented confirming that the randomized approach might be competitive to modern deterministic convex optimization methods. Keywords: onvex Optimization, Randomized Algorithms, Hit and Run, Linear Matrix Inequalities Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: Download: [PDF] Entry Submitted: 12/01/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  