期刊
MATHEMATICAL PROGRAMMING
卷 103, 期 3, 页码 427-444出版社
SPRINGER
DOI: 10.1007/s10107-004-0564-1
关键词
semidefinite programming; low-rank matrices; vector programming; combinatorial optimization; nonlinear programming; augmented Lagrangian; numerical experiments
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据