Procedura-S

Procedura S este o teoremă care stabilește condițiile în care o anumită inegalitate pătratică este o consecință a unei alte inegalități pătratice. Acest rezultat a fost dezvoltat independent în diferite contexte ^[1] ^[2] și își găsește aplicația în teoria controlului , algebra liniară și optimizare .

Declarația procedurii-S

Luați în considerare matrici simetrice $A_{1},A_{2}\in S^{n}$ ${\ displaystyle A_ {1}, A_ {2} \ în S ^ {n}}$ ${\ displaystyle A_ {1}, A_ {2} \ în S ^ {n}}$ , vectori $b_{1},b_{2}\in \mathbb {R} ^{n}$ ${\ displaystyle b_ {1}, b_ {2} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle b_ {1}, b_ {2} \ in \ mathbb {R} ^ {n}}$ , două numere reale $c_{1},c_{2}\in \mathbb {R}$ ${\ displaystyle c_ {1}, c_ {2} \ in \ mathbb {R}}$ ${\ displaystyle c_ {1}, c_ {2} \ in \ mathbb {R}}$ și să presupunem că există un ${\hat {x}}$ ${\ displaystyle {\ hat {x}}}$ ${\ displaystyle {\ hat {x}}}$ pentru care merită ${\hat {x}}^{T}A_{2}{\hat {x}}+2b_{2}^{T}{\hat {x}}+c_{2}<0\,.$ ${\ displaystyle {\ hat {x}} ^ {T} A_ {2} {\ hat {x}} + 2b_ {2} ^ {T} {\ hat {x}} + c_ {2} <0 \, .}$ ${\ displaystyle {\ hat {x}} ^ {T} A_ {2} {\ hat {x}} + 2b_ {2} ^ {T} {\ hat {x}} + c_ {2} <0 \, .}$ Apoi, există un $x\in \mathbb {R} ^{n}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ pe care o satisfaci

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\,,

{\ displaystyle 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 \ ,,}

{\ displaystyle 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 \ ,,}

dacă și numai dacă nu există $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ astfel încât

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

{\ displaystyle \ 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.}

{\ displaystyle \ 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.}

Această teoremă, care poate fi considerată o teoremă a alternativelor, poate fi enunțată sub următoarea formă: implicație

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\,,

{\ displaystyle 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 \ ,,}

{\ displaystyle 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 \ ,,}

deține dacă și numai dacă a $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ astfel încât

\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}}\,,

{\ displaystyle \ 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}} \ ,,}

{\ displaystyle \ 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}} \ ,,}

presupunând că există un punct ${\hat {x}}$ ${\ displaystyle {\ hat {x}}}$ ${\ displaystyle {\ hat {x}}}$ pentru care ${\hat {x}}^{T}A_{1}{\hat {x}}+2b_{1}^{T}{\hat {x}}+c_{1}<0\,.$ ${\ displaystyle {\ hat {x}} ^ {T} A_ {1} {\ hat {x}} + 2b_ {1} ^ {T} {\ hat {x}} + c_ {1} <0 \, .}$ ${\ displaystyle {\ hat {x}} ^ {T} A_ {1} {\ hat {x}} + 2b_ {1} ^ {T} {\ hat {x}} + c_ {1} <0 \, .}$ ^[3]

Notă

^ Frank Uhlig, O teoremă recurentă despre perechi de forme și extensii pătratice: o cercetare , Algebra liniară și aplicațiile sale, volumul 25, 1979, paginile 219–237.
^ Imre Pólik și Tamás Terlaky, A Survey of the S-Lemma , SIAM Review, Volumul 49, 2007, paginile 371-418.
^ Stephen Boyd și Lieven Vandenberghe,Convex Optimization ( PDF ), pe web.stanford.edu , Cambridge University Press, 2004, p. 655.

[1] Frank Uhlig, O teoremă recurentă despre perechi de forme și extensii pătratice: o cercetare , Algebra liniară și aplicațiile sale, volumul 25, 1979, paginile 219–237.

[2] Imre Pólik și Tamás Terlaky, A Survey of the S-Lemma , SIAM Review, Volumul 49, 2007, paginile 371-418.

[3] Stephen Boyd și Lieven Vandenberghe,Convex Optimization ( PDF ), pe web.stanford.edu , Cambridge University Press, 2004, p. 655.

[1]

[2]

[3]