Optimization Online


Local Minima and Convergence in Low-Rank Semidefinite Programming

Samuel Burer (samuel-burer***at***uiowa.edu)
Renato Monteiro (monteiro***at***isye.gatech.edu)

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.


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
Entry Accepted: 09/29/2003
Entry Last Modified: 09/29/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society