S-procedure
From HandWiki
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 F1 and F2 be symmetric matrices, g1 and g2 be vectors and h1 and h2 be real numbers. Assume that there is some x0 such that the strict inequality [math]\displaystyle{ x_0^T F_1 x_0 + 2g_1^T x_0 + h_1 \lt 0 }[/math] holds. Then the implication
- [math]\displaystyle{ x^T F_1 x + 2g_1^T x + h_1 \le 0 \Longrightarrow x^T F_2 x + 2g_2^T x + h_2 \le 0 }[/math]
holds if and only if there exists some nonnegative number λ such that
- [math]\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} }[/math]
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.
See also
 |  |
