S-procedure

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^[1]^[2] 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 $x_{0}^{T}F_{1}x_{0}+2g_{1}^{T}x_{0}+h_{1}<0$ holds. Then the implication

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

\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.^[3]

References

^ 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.
^ Imre Pólik and Tamás Terlaky, A Survey of the S-Lemma, SIAM Review, Volume 49, 2007, Pages 371–418.
^ Stephen Boyd and Lieven Vandenberghe Convex Optimization, Cambridge University Press, 2004, p.655.

Statement of the S-procedure

References

See also