Journal article
Local minima and convergence in low-rank semidefinite programming
Mathematical programming, Vol.103(3), pp.427-444
07/01/2005
DOI: 10.1007/s10107-004-0564-1
Abstract
The low-rank semidefinite programming problem LRSDP r is a restriction of the semidefinite programming problem SDP in which a bound r is imposed on the rank of X, and it is well known that LRSDP r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP r and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles LRSDP r via the nonconvex change of variables X=RR T . In addition, for particular problem classes, we describe a practical technique for obtaining lower bounds on the optimal solution value during the execution of the algorithm. Computational results are presented on a set of combinatorial optimization relaxations, including some of the largest quadratic assignment SDPs solved to date. © Springer-Verlag 2004.
Details
- Title: Subtitle
- Local minima and convergence in low-rank semidefinite programming
- Creators
- Samuel Burer - University of IowaRenato D. C Monteiro - Georgia Institute of Technology
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.103(3), pp.427-444
- Publisher
- Springer
- DOI
- 10.1007/s10107-004-0564-1
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Language
- English
- Date published
- 07/01/2005
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380425902771
Metrics
9 Record Views