On the Burer–Monteiro method for general semidefinite programs
Abstract Consider a semidefinite program involving an $$n\times n$$ n × n...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136891 |
| _version_ | 1811077364688355328 |
|---|---|
| author | Cifuentes, Diego |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Cifuentes, Diego |
| author_sort | Cifuentes, Diego |
| collection | MIT |
| description | Abstract
Consider a semidefinite program involving an
$$n\times n$$
n
×
n
positive semidefinite matrix X. The Burer–Monteiro method uses the substitution
$$X=Y Y^T$$
X
=
Y
Y
T
to obtain a nonconvex optimization problem in terms of an
$$n\times p$$
n
×
p
matrix Y. Boumal et al. showed that this nonconvex method provably solves equality-constrained semidefinite programs with a generic cost matrix when
$$p > rsim \sqrt{2m}$$
p
≳
2
m
, where m is the number of constraints. In this note we extend their result to arbitrary semidefinite programs, possibly involving inequalities or multiple semidefinite constraints. We derive similar guarantees for a fixed cost matrix and generic constraints. We illustrate applications to matrix sensing and integer quadratic minimization. |
| first_indexed | 2024-09-23T10:41:46Z |
| format | Article |
| id | mit-1721.1/136891 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:41:46Z |
| publishDate | 2021 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1368912023-02-17T17:47:15Z On the Burer–Monteiro method for general semidefinite programs Cifuentes, Diego Massachusetts Institute of Technology. Department of Mathematics Abstract Consider a semidefinite program involving an $$n\times n$$ n × n positive semidefinite matrix X. The Burer–Monteiro method uses the substitution $$X=Y Y^T$$ X = Y Y T to obtain a nonconvex optimization problem in terms of an $$n\times p$$ n × p matrix Y. Boumal et al. showed that this nonconvex method provably solves equality-constrained semidefinite programs with a generic cost matrix when $$p > rsim \sqrt{2m}$$ p ≳ 2 m , where m is the number of constraints. In this note we extend their result to arbitrary semidefinite programs, possibly involving inequalities or multiple semidefinite constraints. We derive similar guarantees for a fixed cost matrix and generic constraints. We illustrate applications to matrix sensing and integer quadratic minimization. 2021-11-01T14:34:01Z 2021-11-01T14:34:01Z 2021-01-28 2021-08-14T03:24:48Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/136891 en https://doi.org/10.1007/s11590-021-01705-4 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The Author(s), under exclusive licence to Springer-Verlag GmbH, DE part of Springer Nature application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Cifuentes, Diego On the Burer–Monteiro method for general semidefinite programs |
| title | On the Burer–Monteiro method for general semidefinite programs |
| title_full | On the Burer–Monteiro method for general semidefinite programs |
| title_fullStr | On the Burer–Monteiro method for general semidefinite programs |
| title_full_unstemmed | On the Burer–Monteiro method for general semidefinite programs |
| title_short | On the Burer–Monteiro method for general semidefinite programs |
| title_sort | on the burer monteiro method for general semidefinite programs |
| url | https://hdl.handle.net/1721.1/136891 |
| work_keys_str_mv | AT cifuentesdiego ontheburermonteiromethodforgeneralsemidefiniteprograms |