The S-lemma tackles an issue about quadratic implication in quadratic optimization, control theory, and robust optimization. It provides conditions under which one quadratic inequality is implied by another and therefore forms an important bridge between nonconvex quadratic problems and convex optimization techniques. Generally spoken, quadratic feasibility is NP-hard, yet the S-Lemma identifies a possibility of polynomial solvability. In other words, the time required by an algorithm to find a solution scales as a polynomial function of the input size n and are thus considered efficiently computable.
Historically, the result emerged from the development of theorems of the alternative, beginning with linear results such as Farkas’ Lemma and later extending to quadratic settings through the work of Finsler, Dines, Yakubovich, and many others. In modern optimization theory, the S-lemma plays a central role in semidefinite programming, robust optimization, and the analysis of quadratically constrained problems.
A key motivation for studying the S-lemma lies in its connection to Linear Matrix Inequalities (LMIs).
Many nonconvex quadratic optimization problems can be reformulated as semidefinite programs by replacing rank-one matrices of the form Z = zz⊤ with the relaxed semidefinite constraint Z 0. The S-lemma provides theoretical conditions under which such relaxations are exact and therefore allows difficult quadratic problems to be solved efficiently with convex optimization methods. This connection is particularly important in modern applications, where LMIs appear in control theory, signal processing, and robust optimization. Closely related to this development is Farkas’ Lemma, one of the classical theorems
of the alternative in linear optimization. It establishes a duality principle for linear systems and can be interpreted geometrically as a separation theorem for convex cones. The S-lemma can be viewed as a nonlinear and nonconvex extension of this fundamental idea to quadratic systems because it guarantees that infeasibility of a pair of quadratic inequalities is certified by the existence of a non-negative scalar multiplier λ such that the linear combination of the associated symmetric matrices becomes positive semidefinite, playing the same role as the non-negative multipliers in the classical linear Farkas certificate.
- Quote paper
- Tristan Verheylewegen (Author), 2026, The S-Lemma, Munich, GRIN Verlag, https://www.grin.com/document/1736843
