On the local stability of semidefinite relaxations

Diego Cifuentes, Sameer Agarwal, Pablo A. Parrilo, Rekha R. ThomasMath. Program 2022 · DOI

Introduction

Many fundamental problems in engineering, robotics, and computer vision—such as 3D reconstruction and rotation synchronization—are formulated as Quadratically Constrained Quadratic Programs (QCQPs). While these problems are generally NP-hard, practitioners frequently employ Semidefinite Programming (SDP) relaxations to transform them into tractable convex optimizations. Although these relaxations theoretically only provide lower bounds, they often exhibit a "miracle" in practice: in low-noise regimes, the relaxation is frequently tight, yielding the exact global optimum of the original non-convex problem. This paper provides a theoretical foundation explaining why and when this tightness is stable under perturbations.

Theoretical Framework: Defining SDP Stability

The authors introduce the concept of SDP stability to characterize the robustness of zero duality gaps. A problem is considered SDP-stable if there exists a neighborhood around a "nominal" parameter (typically representing a noiseless measurement) within which the duality gap remains zero.

To establish this stability, the research identifies several critical regularity conditions:

  • Abadie Constraint Qualification (ACQ): This ensures the feasible set is sufficiently "smooth" at the solution point.
  • Restricted Slater Condition: In scenarios where dual solutions are non-unique, this condition ensures the existence of a "good" dual solution that certifies primal optimality. This can be checked efficiently through an auxiliary SDP.
  • Homogenization: The paper provides a systematic method to apply these theories to inhomogeneous problems (those containing linear terms) by converting them into a homogeneous format.

Applications and Benchmarks

The theory is validated across a diverse set of classic estimation and computer vision problems, demonstrating its broad applicability:

  • Rotation & SE(d) Synchronization in robotics.
  • Camera Triangulation and Resectioning in vision.
  • Tensor PCA and Essential Matrix Estimation.
  • Approximate Greatest Common Divisor (GCD) problems.

Key Insights: The Geometry of Tightness

A central insight of the work is that tightness is a local property tied to the geometry of the underlying algebraic variety. If a solution point is a singular point or a "branch point" of the variety, the relaxation's stability may be compromised. Furthermore, the authors demonstrate that their results extend to higher levels of the Sum-of-Squares (SOS) hierarchy, explaining why some problems that fail to be tight at the first level of relaxation become stable at the second.

Key Results

The core of the paper lies in Theorems 3.2 and 4.5, which provide formal conditions under which an SDP relaxation is guaranteed to be stable. The authors use the "twisted cubic" curve as a primary illustrative example to visualize these theoretical bounds.

Visualization of the SDP-exact region for the twisted cubic curve. The green-dotted region indicates where the duality gap is zero, demonstrating the stability of the relaxation around the central curve.

As shown in the figure, the "SDP-exact region" (where the duality gap is zero) forms a stable neighborhood around the nominal parameters. The theoretical inner approximations developed in the paper fit within this region, providing a checkable certificate for when a practitioner can trust the SDP solution to be globally optimal.

Conclusion and Future Work

This research successfully unifies previously disconnected observations in various fields under a single theoretical lens. It proves that the "miracle" of zero duality gaps is not a fragile fluke but a mathematically guaranteed consequence of local stability.

However, some limitations remain. The current framework focuses primarily on equality-constrained problems; while it can handle inequality constraints that remain "active," a more comprehensive treatment of general inequalities is a subject for future study. Additionally, the theory assumes the existence of a nominal point where the relaxation is already tight. Determining the global boundaries of tightness in high-noise regimes remains an open challenge for the optimization community.

Summary updated

BibTeX
@article{cifuentes2022local,
  author = {Diego Cifuentes and Sameer Agarwal and Pablo A. Parrilo and Rekha R. Thomas},
  title = {{On the local stability of semidefinite relaxations}},
  journal = {Math. Program.},
  year = {2022},
  doi = {10.1007/s10107-021-01696-1},
}
Figure