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 contextsFrank Uhlig, [https://dx.doi.org/10.1016/0024-3795(79)90020-X 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, [https://dx.doi.org/10.1137/S003614450444614X A Survey of the S-Lemma], SIAM Review, Volume 49, 2007, Pages 371–418. 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 holds. Then the implication

::$x^T\; F\_1\; x\; +\; 2g\_1^T\; x\; +\; h\_1\; \backslash le\; 0\; \backslash Longrightarrow\; x^T\; F\_2\; x\; +\; 2g\_2^T\; x\; +\; h\_2\; \backslash le\; 0$

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

::

is positive semidefinite.Stephen Boyd and Lieven Vandenberghe [https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization], Cambridge University Press, 2004, p.655.