Optimization Online


On the local stability of semidefinite relaxations

Diego Cifuentes(diegcif***at***mit.edu)
Sameer Agarwal(sameeragarwal***at***google.com)
Pablo A. Parrilo(parrilo***at***mit.edu)
Rekha R. Thomas( rrthomas***at***uw.edu)

Abstract: In this paper we consider a parametric family of polynomial optimization problems over algebraic sets. Although these problems are typically nonconvex, tractable convex relaxations via semidefinite programming (SDP) have been proposed. Often times in applications there is a natural value of the parameters for which the relaxation will solve the problem exactly. We study conditions (and quantitative bounds) under which the relaxation will continue to be exact as the parameter moves in a neighborhood of the original one. It suffices to restrict to quadratically constrained quadratic programs. Our framework captures several estimation problems such as low rank approximation, camera triangulation, rotation synchronization, approximate matrix completion and approximate GCD. In these applications, a solution is easy under noiseless observations, and our results guarantee that the SDP relaxation will continue to solve the problem in the low noise regime.

Keywords: Parametric SDP, Stability, Sum of squares, Algebraic variety

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Applications -- Science and Engineering


Download: [PDF]

Entry Submitted: 12/04/2017
Entry Accepted: 12/04/2017
Entry Last Modified: 12/04/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society