- | ||||
|
![]()
|
Local Minima and Convergence in Low-Rank Semidefinite Programming
Samuel Burer (samuel-burer 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 \cite{BurMon03-1}, 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. Keywords: Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 2: Combinatorial Optimization Citation: Technical report, Department of Management Sciences, University of Iowa, September 2003. Download: [Postscript][PDF] Entry Submitted: 09/29/2003 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 | |
![]() |