DocumentCode :
2250172
Title :
A randomized cutting plane scheme with geometric convergence: Probabilistic analysis and SDP applications
Author :
Dabbene, F. ; Shcherbakov, P. ; Polyak, B.T.
Author_Institution :
IEIIT-CNR, Turin, Italy
fYear :
2008
fDate :
9-11 Dec. 2008
Firstpage :
3044
Lastpage :
3049
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. 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.
Keywords :
computational geometry; convergence of numerical methods; convex programming; estimation theory; minimisation; probability; random processes; randomised algorithms; convex body; convex optimization problem; geometric convergence; linear function minimization; probability estimation; randomized cutting plane scheme; semidefinite programming; uniform generating-oracle; Algorithm design and analysis; Constraint optimization; Convergence; Cost function; Gravity; Minimization methods; Monte Carlo methods; Optimization methods; Probability;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control, 2008. CDC 2008. 47th IEEE Conference on
Conference_Location :
Cancun
ISSN :
0191-2216
Print_ISBN :
978-1-4244-3123-6
Electronic_ISBN :
0191-2216
Type :
conf
DOI :
10.1109/CDC.2008.4739188
Filename :
4739188
Link To Document :
بازگشت