A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-rank Factorization
Authors: Samuel Burer, Renato D.C. Monteiro
Liked by: Maximimi
Domains: Optimisation
Tags: SDP
Uploaded by: Maximimi
Upload date: 2018-05-25 12:10:25


### Nice and promising heuristic for large and sparse SDP "we present computational results which show that the method finds optimal solutions to (2) quite reliably, and although we are able to derive some amount of theoretical justification for this, our belief that the method is not strongly affected by the inherent nonconvexity of (2) is largely experimental" ### Optimality I read: "Theorem 2.2. There exists an optimal solution $X^∗$ of (1) with rank r satisfying the inequality $r(r+ 1)/2 ≤ m$.", where (1) is the standard-form primal SDP and $m$ is the number of linear constraints in the SDP. Is there a proof that with $r>\sqrt{2m}$, SDPLR gives the optimal solution? i.e. any local minimum is a global minimum? ### Goemans-Williamson SDP relaxation This is an algorithm that seems more scalable: https://github.com/maxdan94/spingraphSDP
Maximimi at 2018-06-14 15:31:51
Edited by Maximimi at 2018-06-14 15:55:23
Survey paper: [Low-Rank Semidefinite Programming: Theory and Applications](http://www1.se.cuhk.edu.hk/~manchoso/papers/low_rank-FnT_Opt.pdf)
Maximimi at 2018-06-14 15:42:11
Edited by Maximimi at 2018-06-14 15:43:44

Please consider to register or login to comment on the paper.