Procedura-S

Template:O 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 {ℝ}^n$, due numeri reali $c_1,c_2\in ℝ$ 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 {ℝ}^n$che soddisfi

$x^T{A}_{1}x+2b_1^{T}x+c_1<0,x^T{A}_{2}x+2b_2^{T}x+c_2\le 0,$

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

$\lambda \ge 0,\left[\begin{array}{cc}{A}_1& b_1\\ b_1^T& c_1\end{array}\right]+\lambda \left[\begin{array}{cc}{A}_2& b_2\\ b_2^T& c_2\end{array}\right]⪰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\le 0⟹x^T{A}_{2}x+2b_2^{T}x+c_2\le 0,$

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

$\lambda \ge 0,\left[\begin{array}{cc}{A}_2& b_2\\ b_2^T& c_2\end{array}\right]⪯\lambda \left[\begin{array}{cc}{A}_1& b_1\\ b_1^T& c_1\end{array}\right],$

ammesso che esista un punto $\hat{x}$ per cui ${\hat{x}}^T{A}_1\hat{x}+2b_1^T\hat{x}+c_1<0.$