Умова Слейтера

Умова Слейтера — це достатня умова для сильної двоїстості в задачі опуклої оптимізації. Умову названо ім'ям Мортона Л. Слейтера. Неформально, умова Слейтера стверджує, що допустима область повинна мати внутрішню точку (див. подробиці нижче).

Умова Слейтера є прикладом умов регулярності . Зокрема, якщо умова Слейтера виконується для прямої задачі, то розрив двоїстості дорівнює 0 і якщо значення двоїстої задачі скінченне, воно досягається.

Формулювання

Розглянемо задачу оптимізації: Мінімізувати $f_{0}(x)$

За обмежень

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

$Ax=b$ ,

де $f_{0},\ldots ,f_{m}$ — опуклі функції. Це випадок задачі опуклого програмування.

Іншими словами, умова Слейтера для опуклого програмування стверджує, що сильна двоїстість виконується, якщо є точка $x^{*}$, така, що $x^{*}$ лежить строго всередині області допустимих розв'язків (тобто всі обмеження виконуються, а нелінійні обмеження виконуються як строгі нерівності).

Математично умова Слейтера стверджує, що сильна двоїстість виконується, якщо існує точка $x^{*}\in \operatorname {relint} (D)$ (де relint позначає відносну внутрішність опуклої множини $D:=\cap _{i=0}^{m}\operatorname {dom} (f_{i})$), така, що

$f_{i}(x^{*})<0,i=1,\ldots ,m,$ (опуклі нелінійні обмеження)

$Ax^{*}=b$.

Узагальнені нерівності

Нехай дано задачу: Мінімізувати $f_{0}(x)$

За обмежень

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

$Ax=b$ ,

де функція $f_{0}$ опукла, а $f_{i}$$K_{i}$ — опукла для будь-якого $i$. Тоді умова Слейтера каже, що у випадку, коли існує $x^{*}\in \operatorname {relint} (D)$, таке, що

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

$Ax^{*}=b,$

то має місце сильна двоїстість.

Література

• Morton Slater. Cowles Commission Discussion Paper No. 403. — 1950. Передруковано в
  • Traces and Emergence of Nonlinear Programming / Giorgio Giorgi, Tinne Hoff Kjeldsen. — Basel : Birkhäuser, 2014. — С. 293–306. — ISBN 978-3-0348-0438-7.
• Akira Takayama. Mathematical Economics. — New York : Cambridge University Press, 1985. — ISBN 0-521-25707-7.
• Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2nd. — Springer, 2006. — ISBN 0-387-29570-4.
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — ISBN 978-0-521-83378-3.