The geometry of SDP-exactness in quadratic optimization
Abstract Consider the problem of minimizing a quadratic objective subject to quadratic equations. We study the semialgebraic region of objective functions for which this problem is solved by its semidefinite relaxation. For the Euclidean distance problem, this is a bundle of spectrahedral shadows s...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131668 |
| _version_ | 1826200543189532672 |
|---|---|
| author | Cifuentes, Diego Harris, Corey Sturmfels, Bernd |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Cifuentes, Diego Harris, Corey Sturmfels, Bernd |
| author_sort | Cifuentes, Diego |
| collection | MIT |
| description | Abstract
Consider the problem of minimizing a quadratic objective subject to quadratic equations. We study the semialgebraic region of objective functions for which this problem is solved by its semidefinite relaxation. For the Euclidean distance problem, this is a bundle of spectrahedral shadows surrounding the given variety. We characterize the algebraic boundary of this region and we derive a formula for its degree. |
| first_indexed | 2024-09-23T11:38:01Z |
| format | Article |
| id | mit-1721.1/131668 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:38:01Z |
| publishDate | 2021 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1316682023-09-19T20:27:11Z The geometry of SDP-exactness in quadratic optimization Cifuentes, Diego Harris, Corey Sturmfels, Bernd Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Abstract Consider the problem of minimizing a quadratic objective subject to quadratic equations. We study the semialgebraic region of objective functions for which this problem is solved by its semidefinite relaxation. For the Euclidean distance problem, this is a bundle of spectrahedral shadows surrounding the given variety. We characterize the algebraic boundary of this region and we derive a formula for its degree. 2021-09-20T17:29:30Z 2021-09-20T17:29:30Z 2019-05-15 2020-06-26T12:53:39Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131668 PUBLISHER_CC en https://doi.org/10.1007/s10107-019-01399-8 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Cifuentes, Diego Harris, Corey Sturmfels, Bernd The geometry of SDP-exactness in quadratic optimization |
| title | The geometry of SDP-exactness in quadratic optimization |
| title_full | The geometry of SDP-exactness in quadratic optimization |
| title_fullStr | The geometry of SDP-exactness in quadratic optimization |
| title_full_unstemmed | The geometry of SDP-exactness in quadratic optimization |
| title_short | The geometry of SDP-exactness in quadratic optimization |
| title_sort | geometry of sdp exactness in quadratic optimization |
| url | https://hdl.handle.net/1721.1/131668 |
| work_keys_str_mv | AT cifuentesdiego thegeometryofsdpexactnessinquadraticoptimization AT harriscorey thegeometryofsdpexactnessinquadraticoptimization AT sturmfelsbernd thegeometryofsdpexactnessinquadraticoptimization AT cifuentesdiego geometryofsdpexactnessinquadraticoptimization AT harriscorey geometryofsdpexactnessinquadraticoptimization AT sturmfelsbernd geometryofsdpexactnessinquadraticoptimization |