S-lemma with equality and its applications

Yong Xia, Shu Wang, Ruey-Lin SheuMath. Program 2016 · DOI

TL;DR

This paper introduces a powerful new characterization of the "S-lemma with equality," a fundamental result in optimization theory. By precisely defining when this lemma holds, the authors unlock novel, condition-free methods for solving challenging quadratic programming problems and characterizing the convexity of complex numerical ranges.

What Problem Does This Paper Address?

The S-lemma is a cornerstone result in optimization, particularly in the context of quadratic programming with inequality constraints. The "classical S-lemma" establishes an equivalence between the unsolvability of a system involving a quadratic inequality and the existence of a linear combination of quadratic functions that is always non-negative. However, a related problem, the "S-lemma with equality," which deals with quadratic equality constraints, has been notoriously difficult to characterize. Specifically, the equivalence between the unsolvability of $h(x)=0 \implies f(x) \ge 0$ and the existence of a scalar $\mu$ such that $f(x) + \mu h(x) \ge 0$ does not always hold. This paper aims to precisely identify the conditions under which this "S-lemma with equality" does hold, thereby extending its applicability to a wider range of optimization problems.

Methods

The authors tackle this problem by systematically analyzing different cases based on the properties of the quadratic functions involved, particularly the constraint function $h(x)$. They leverage Finsler's Theorem, a foundational result in quadratic forms, and introduce a homogenization technique to transform non-homogeneous problems into homogeneous ones, simplifying analysis. A key aspect of their approach is the detailed breakdown of cases, including when the constraint function $h(x)$ takes both positive and negative values (Assumption 1) and when it does not. They also introduce a "regularized S-lemma with equality" as a more general result that holds even when the standard conditions are not met. The paper then applies these characterizations to solve problems like the generalized trust region subproblem and analyze the convexity of joint numerical ranges.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Precise Characterization of S-lemma with Equality: The paper provides a complete and precise characterization of when the S-lemma with equality holds, identifying specific conditions related to the eigenvalues of the matrices involved and the properties of the constraint function. This was a long-standing open problem.
  • Unlocking Condition-Free Solutions: By precisely understanding the S-lemma with equality, the authors can now solve important optimization problems, such as the quadratic programming with a single quadratic equality constraint (QP1EQC) and the generalized trust region subproblem (GTRS), without requiring any prior assumptions like Slater's condition or the existence of a positive definite matrix pencil.
  • Bridging the Gap Between Inequality and Equality: The work clarifies the relationship between the S-lemma for inequalities and the more challenging S-lemma for equalities, showing how the latter can be used to derive results for the former under certain conditions.
  • New Insights into Convexity: The paper provides a new characterization for the convexity of joint numerical ranges of quadratic functions and affine functions, extending previous results and offering a more unified framework.

Key Results

  • Theorem 3: Provides a necessary and sufficient condition for the S-lemma with equality to hold when the constraint function $h(x)$ takes both positive and negative values. This condition is expressed in terms of the eigenvalues of the matrices and the null space of $B$.
  • Theorem 1 & 2: Characterize the S-lemma with equality and a "regularized" version when Assumption 1 (h(x) takes both positive and negative values) is violated.
  • Application to QP1EQC: The paper shows how the S-lemma with equality can be used to solve the quadratic programming with a single quadratic equality constraint (QP1EQC) directly via a semidefinite programming (SDP) relaxation, without any assumptions.
  • Application to GTRS: The generalized trust region subproblem (GTRS) is also completely solved without any conditions, building upon the results for QP1EQC.
  • Theorem 9: Offers a new condition for the convexity of joint numerical ranges of quadratic functions and affine functions.

Limitations and Future Work

  • Complexity of Proofs: The authors acknowledge that the proofs for the S-lemma with equality are intricate, often relying on detailed algebraic manipulations and case analysis, which can make them less intuitive.
  • Generalization to More Constraints: While the paper focuses on a single quadratic equality constraint, future work could explore extending these results to systems with multiple quadratic equality constraints.
  • Algorithmic Implications: While the paper provides theoretical solutions, further research could focus on developing efficient algorithms that leverage these new theoretical insights for practical applications.
  • Exploration of Specific Cases: The paper meticulously analyzes various cases, but there might be further nuances or special scenarios that could be explored for deeper understanding.

Summary updated

BibTeX
@article{xia2016s,
  author = {Yong Xia and Shu Wang and Ruey-Lin Sheu},
  title = {{S-lemma with equality and its applications}},
  journal = {Math. Program.},
  year = {2016},
  doi = {10.1007/s10107-015-0907-0},
}
Figure