On the local stability of semidefinite relaxations
Abstract We consider a parametric family of quadratically constrained quadratic programs and their associated semidefinite programming (SDP) relaxations. Given a nominal value of the parameter at which the SDP relaxation is exact, we study conditions (and quantitative bounds) under wh...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2022
|
| Online Access: | https://hdl.handle.net/1721.1/142958 |
| _version_ | 1826207237602803712 |
|---|---|
| author | Cifuentes, Diego Agarwal, Sameer Parrilo, Pablo A. Thomas, Rekha R. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cifuentes, Diego Agarwal, Sameer Parrilo, Pablo A. Thomas, Rekha R. |
| author_sort | Cifuentes, Diego |
| collection | MIT |
| description | Abstract
We consider a parametric family of quadratically constrained quadratic programs and their associated semidefinite programming (SDP) relaxations. Given a nominal value of the parameter at which the SDP relaxation is exact, we study conditions (and quantitative bounds) under which the relaxation will continue to be exact as the parameter moves in a neighborhood around the nominal value. Our framework captures a wide array of statistical estimation problems including tensor principal component analysis, rotation synchronization, orthogonal Procrustes, camera triangulation and resectioning, essential matrix estimation, system identification, and approximate GCD. Our results can also be used to analyze the stability of SOS relaxations of general polynomial optimization problems. |
| first_indexed | 2024-09-23T13:46:31Z |
| format | Article |
| id | mit-1721.1/142958 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:46:31Z |
| publishDate | 2022 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1429582023-04-10T18:54:53Z On the local stability of semidefinite relaxations Cifuentes, Diego Agarwal, Sameer Parrilo, Pablo A. Thomas, Rekha R. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Abstract We consider a parametric family of quadratically constrained quadratic programs and their associated semidefinite programming (SDP) relaxations. Given a nominal value of the parameter at which the SDP relaxation is exact, we study conditions (and quantitative bounds) under which the relaxation will continue to be exact as the parameter moves in a neighborhood around the nominal value. Our framework captures a wide array of statistical estimation problems including tensor principal component analysis, rotation synchronization, orthogonal Procrustes, camera triangulation and resectioning, essential matrix estimation, system identification, and approximate GCD. Our results can also be used to analyze the stability of SOS relaxations of general polynomial optimization problems. 2022-06-13T12:42:24Z 2022-06-13T12:42:24Z 2021-09-03 2022-06-11T03:23:05Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/142958 Cifuentes, Diego, Agarwal, Sameer, Parrilo, Pablo A. and Thomas, Rekha R. 2021. "On the local stability of semidefinite relaxations." en https://doi.org/10.1007/s10107-021-01696-1 Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International https://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Cifuentes, Diego Agarwal, Sameer Parrilo, Pablo A. Thomas, Rekha R. On the local stability of semidefinite relaxations |
| title | On the local stability of semidefinite relaxations |
| title_full | On the local stability of semidefinite relaxations |
| title_fullStr | On the local stability of semidefinite relaxations |
| title_full_unstemmed | On the local stability of semidefinite relaxations |
| title_short | On the local stability of semidefinite relaxations |
| title_sort | on the local stability of semidefinite relaxations |
| url | https://hdl.handle.net/1721.1/142958 |
| work_keys_str_mv | AT cifuentesdiego onthelocalstabilityofsemidefiniterelaxations AT agarwalsameer onthelocalstabilityofsemidefiniterelaxations AT parrilopabloa onthelocalstabilityofsemidefiniterelaxations AT thomasrekhar onthelocalstabilityofsemidefiniterelaxations |