Stare Slater

Condiția Slater este o condiție suficientă pentru dualitate strictă într- o problemă de optimizare convexă . Condiția este numită după Morton L. Slater [1] . În mod informal, condiția Slater afirmă că o regiune validă trebuie să aibă un punct interior (vezi detaliile de mai jos).

Condiția Slater este un exemplu de condiții de regularitate [2] . În special, dacă condiția Slater este satisfăcută pentru problema primară , atunci decalajul de dualitate este 0 și, dacă valoarea problemei duale este finită, se atinge [3] .

Formulare

Luați în considerare problema de optimizare

Minimizați

f_{0}(x)

Cu restricții

f_{i}(x)\leqslant 0,i=1,\ldots,m

ax=b

unde sunt funcții convexe . Aceasta este o instanță a unei probleme de programare convexă . $f_{0},\ldots,f_{m)$

Cu alte cuvinte, condiția Slater pentru programarea convexă afirmă că dualitatea puternică este valabilă dacă există un punct care se află strict în domeniul soluțiilor fezabile (adică, toate constrângerile sunt valabile, dar constrângerile neliniare sunt valabile ca inegalități stricte). $x^{*}$ $x^{*}$

Din punct de vedere matematic, condiția Slater afirmă că dualitatea puternică este valabilă dacă există un punct (unde reluare denotă interiorul relativ al unei mulțimi convexe ) astfel încât $x^{*}\in \operatorname {relint} (D)$ $D:=\cap _{i=0}^{m}\operatorname {dom} (f_{i})$

f_{i}(x^{*})<0,i=1,\ldots ,m,

(constrângeri neliniare convexe)

Ax^{*}=b.\,

[4] .

Inegalități generalizate

Lasă sarcina să fie dată

Minimizați

f_{0}(x)

Cu restricții

f_{i}(x)\leqslant _{K_{i}}0,i=1,\ldots,m

ax=b

unde funcția este convexă și este convexă pentru orice . Atunci condiția Slater spune că, în cazul în care există , astfel încât $f_0$ $f_{i}$ $K_{i}$ $i$ $x^{*}\in \operatorname {relint} (D)$

f_{i}(x^{*})<_{K_{i}}0,i=1,\ldots ,m

și

Ax^{*}=b

atunci există dualitate strictă [4] .

Note

↑ Slater, 1950 .
↑ Takayama, 1985 , p. 66–76.
↑ Borwein, Lewis, 2006 .
↑ 1 2 Boyd, Vandenberghe, 2004 .

Literatură

Morton Slater. Documentul de discuție al Comisiei Cowles nr. 403 . - 1950. Retipărit în
- Urmele și apariția programării neliniare / Giorgio Giorgi, Tinne Hoff Kjeldsen. — Basel: Birkhäuser, 2014. — p. 293–306. — ISBN 978-3-0348-0438-7 .
Akira Takayama. Economie matematică . - New York: Cambridge University Press, 1985. - ISBN 0-521-25707-7 .
Jonathan Borwein, Adrian Lewis. Analiza convexă și optimizarea neliniară: teorie și exemple. — al 2-lea. - Springer, 2006. - ISBN 0-387-29570-4 .
Stephen Boyd, Lieven Vandenberghe. Optimizare convexă . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .