Misplaced Pages

The S-procedure or S-lemma is a mathematical result that gives conditions under which a particular quadratic inequality is a consequence of another quadratic inequality. The S-procedure was developed independently in a number of different contexts and has applications in control theory, linear algebra and mathematical optimization.

Statement of the S-procedure

Let F₁ and F₂ be symmetric matrices, g₁ and g₂ be vectors and h₁ and h₂ be real numbers. Assume that there is some x₀ such that the strict inequality ${\displaystyle x_{0}^{T}F_{1}x_{0}+2g_{1}^{T}x_{0}+h_{1}<0}$ holds. Then the implication

${\displaystyle x^{T}F_{1}x+2g_{1}^{T}x+h_{1}\leq 0\Longrightarrow x^{T}F_{2}x+2g_{2}^{T}x+h_{2}\leq 0}$

holds if and only if there exists some nonnegative number λ such that

${\displaystyle \lambda {\begin{bmatrix}F_{1}&g_{1}\\g_{1}^{T}&h_{1}\end{bmatrix}}-{\begin{bmatrix}F_{2}&g_{2}\\g_{2}^{T}&h_{2}\end{bmatrix}}}$

is positive semidefinite.

References

1. Frank Uhlig, A recurring theorem about pairs of quadratic forms and extensions: a survey, Linear Algebra and its Applications, Volume 25, 1979, pages 219–237.
2. Imre Pólik and Tamás Terlaky, A Survey of the S-Lemma, SIAM Review, Volume 49, 2007, Pages 371–418.
3. Stephen Boyd and Lieven Vandenberghe Convex Optimization, Cambridge University Press, 2004, p.655.

See also

• Linear matrix inequality
• Finsler's lemma

• Control theory
• Linear algebra
• Mathematical optimization