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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/s10107-004-0564-1 | Math. Program. |
Keywords | Field | DocType |
semideflnite programming,largest quadratic assignment,low-rank semidefinite programming problem,bound r,nonlinear programming,combinatorial optimization relaxation,local minima,augmented lagrangian,combinatorial optimization,numerical experiments.,low-rank matrices,variables x,computational result,vector programming,particular problem class,low-rank semidefinite programming,optimal convergence,optimal solution value,semidefinite programming problem sdp,lower bound,semidefinite programming | Change of variables,Discrete mathematics,Mathematical optimization,Nonlinear programming,Quadratic equation,Combinatorial optimization,Maxima and minima,Augmented Lagrangian method,Semidefinite embedding,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
103 | 3 | 1436-4646 |
Citations | PageRank | References |
100 | 8.02 | 17 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Samuel Burer | 1 | 1148 | 73.09 |
Renato D. C. Monteiro | 2 | 1250 | 138.18 |