# zbMATH — the first resource for mathematics

Local minima and convergence in low-rank semidefinite programming. (English) Zbl 1099.90040
Summary: The low-rank semidefinite programming problem $$\text{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 $$\text{LRSDP}_r$$ is equivalent to SDP if $$r$$ is not too small. In this paper, we classify the local minima of $$\text{LRSDP}_r$$ and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles $$\text{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.

##### MSC:
 90C22 Semidefinite programming 90C27 Combinatorial optimization
QAPLIB; SDPLR
Full Text: