Procedura-S

La procedura-S è un teorema che stabilisce le condizioni rispetto alle quali una particolare diseguaglianza quadratica è conseguenza di un'altra diseguaglianza quadratica. Tale risultato è stato sviluppato in modo indipendente in diversi contesti e trova applicazione nella teoria del controllo, nell'algebra lineare e nell'ottimizzazione.

Enunciato della procedura-S

Si considerino le matrici simmetriche $A_{1},A_{2}\in S^{n}$, i vettori $b_{1},b_{2}\in \mathbb {R} ^{n}$, due numeri reali $c_{1},c_{2}\in \mathbb {R}$ e si supponga esista un ${\hat {x}}$ per cui valga ${\hat {x}}^{T}A_{2}{\hat {x}}+2b_{2}^{T}{\hat {x}}+c_{2}<0\,.$Allora esiste un $x\in \mathbb {R} ^{n}$che soddisfi

$x^{T}A_{1}x+2b_{1}^{T}x+c_{1}<0\,,\qquad x^{T}A_{2}x+2b_{2}^{T}x+c_{2}\leq 0\,,$

se e solo se non esiste alcun $\lambda$ tale che

$\lambda \geq 0\,,\qquad {\begin{bmatrix}A_{1}&b_{1}\\b_{1}^{T}&c_{1}\end{bmatrix}}+\lambda {\begin{bmatrix}A_{2}&b_{2}\\b_{2}^{T}&c_{2}\end{bmatrix}}\succeq 0.$

Tale teorema, che può essere considerato un teorema delle alternative, può essere enunciato nella seguente forma: l'implicazione

$x^{T}A_{1}x+2b_{1}^{T}x+c_{1}\leq 0\quad \Longrightarrow \quad x^{T}A_{2}x+2b_{2}^{T}x+c_{2}\leq 0\,,$

vale se e solo se esiste un $\lambda$ tale che

$\lambda \geq 0\,,\qquad {\begin{bmatrix}A_{2}&b_{2}\\b_{2}^{T}&c_{2}\end{bmatrix}}\preceq \lambda {\begin{bmatrix}A_{1}&b_{1}\\b_{1}^{T}&c_{1}\end{bmatrix}}\,,$

ammesso che esista un punto ${\hat {x}}$ per cui ${\hat {x}}^{T}A_{1}{\hat {x}}+2b_{1}^{T}{\hat {x}}+c_{1}<0\,.$