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 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.

See also

• Linear matrix inequality
• Finsler's lemma