Abstract
In this paper, we provide an elementary, geometric, and unified framework to analyze conic programs that we call the strict complementarity approach. This framework allows us to establish error bounds and quantify the sensitivity of the solution. The framework uses three classical ideas from convex geometry and linear algebra: linear regularity of convex sets, facial reduction, and orthogonal decomposition. We show how to use this framework to derive error bounds for linear programming (LP), second order cone programming (SOCP), and semidefinite programming (SDP).
Introduction: The Need for Robust Error Bounds
In optimization, finding an exact solution is often computationally impossible or unnecessary. Iterative algorithms typically terminate when a point is "close enough" to optimality. However, "close enough" in terms of objective value or feasibility doesn't always mean "close enough" in terms of actual distance to the optimal solution set. This gap is addressed by Error Bounds (ERB). Furthermore, real-world data is noisy, leading to the question of Sensitivity (SSB): how much does the optimal solution shift when problem parameters (costs $c$ or constraints $A, b$) are perturbed?
While these questions have been studied for decades, existing proofs are often complex, highly specialized to a single type of problem (like just SDP), or fail to provide explicit constants. This paper seeks an "elementary, geometric, and unified" framework that works across the most common types of conic programming.
The Strict Complementarity Framework
The authors propose the Strict Complementarity Approach, which combines three classical tools from convex geometry and linear algebra to simplify the analysis of conic programs.
The approach relies on three pillars:
- Linear Regularity: A property that relates the distance to the intersection of two sets (like a cone and a plane) to the sum of the distances to each set individually.
- Facial Reduction: A technique to "zoom in" on the specific face of a cone where the optimal solution resides. This simplifies the problem by restricting the variable to a smaller subspace ($V_{s_*}$).
- Orthogonal Decomposition: Splitting the entire space into two parts—the subspace containing the solution and its orthogonal complement. This allows the authors to bound errors in each part separately and then combine them.
The "secret sauce" is Strict Complementarity. This condition assumes that the optimal solution doesn't just sit on the boundary of the cone's "slack," but sits in its "relative interior." This prevents certain types of mathematical degeneracy that make error bounds much harder to prove.
Key Insights and Results
The paper shows that LP, SOCP, and SDP aren't just related—they can be analyzed using the exact same geometric "recipe." The only thing that changes is how you calculate the "violation of complementarity" for each specific cone.
Sharpness of Bounds
The paper categorizes the "sharpness" of these bounds using an exponent $p$:
- Linear Programming (LP): The error bound is linear ($p=1$). This matches the classic Hoffman’s Lemma.
- SOCP and SDP: Under strict complementarity, these problems satisfy a quadratic error bound ($p=2$).
Sensitivity via Error Bounds
A major insight is that once you have a solid error bound (ERB), you can derive a sensitivity bound (SSB) almost as a corollary. If you know how suboptimality relates to distance, you can bound how much a perturbation in data affects that suboptimality. This framework allows researchers to estimate actual constants ($c_i$) in terms of the problem's data, provided the primal solution is unique.
Conclusion and Future Work
By viewing error bounds through the lens of distances between sets and subspaces, the authors avoid the dense algebraic proofs common in older literature. While the framework relies heavily on strict complementarity—which holds "generically" in most cases—it fails for certain degenerate problems. Future work involves extending this technique to more complex cones, like copositive or completely positive cones, where characterizing facial structure is a significant challenge.
Summary updated