On the local stability of semidefinite relaxations
Preprint
Abstract
We consider a parametric family of quadratically constrained quadratic programs (QCQP) 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.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- The geometry of SDP-exactness in quadratic optimizationMathematical Programming, 2019
- Phase recovery, MaxCut and complex semidefinite programmingMathematical Programming, 2013
- A QCQP Approach to Triangulation2012
- On zero duality gap in nonconvex quadratic programming problemsJournal of Global Optimization, 2011
- A sensitivity result for semidefinite programsOperations Research Letters, 2004
- Introduction: Set-Valued Analysis in Control TheorySet-Valued Analysis, 2000
- Quadratic maximization and semidefinite relaxationMathematical Programming, 2000
- Algebraic properties of multilinear constraintsMathematical Methods in the Applied Sciences, 1997
- Sensitivity and stability analysis for nonlinear programmingAnnals of Operations Research, 1990
- Fitting conic sections to scattered dataComputer Graphics and Image Processing, 1979