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

You comment anonymously! You will not be able to edit/delete the comment.

Please consider to register or login.

Use $\LaTeX$ to type formulæ and markdown to format text.
When you post something to which you hold the copyright you authorise us to do distribute this data across the scientific community. You can post public domain content. All user-generated content will be freely available online. Please see this page to learn more about Papersγ's terms of use and privacy policy.