Local Minima and Convergence in Low-Rank Semidefinite Programming |
| |
Authors: | Samuel Burer Renato DC Monteiro |
| |
Institution: | (1) Department of Management Sciences, University of Iowa, Iowa City, IA 52242-1000, USA;(2) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA |
| |
Abstract: | The low-rank semidefinite programming problem LRSDPr 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 LRSDPr is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDPr and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro 5], which handles LRSDPr via the nonconvex change of variables X=RRT. 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.This author was supported in part by NSF Grant CCR-0203426.This author was supported in part by NSF Grants CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401. |
| |
Keywords: | Semidefinite programming Low-rank matrices Vector programming Combinatorial optimization Nonlinear programming Augmented Lagrangian Numerical experiments |
本文献已被 SpringerLink 等数据库收录! |
|