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

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

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

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

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

За обмежень

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

${\displaystyle Ax=b}$ ,

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

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

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

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

${\displaystyle Ax^{*}=b}$.

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

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

За обмежень

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

${\displaystyle Ax=b}$ ,

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

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

${\displaystyle Ax^{*}=b,}$

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

Примітки

1. Slater, 1950.
2. Takayama, 1985, с. 66–76.
3. Borwein, Lewis, 2006.
4. Boyd, Vandenberghe, 2004.

Література

• 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. — .
• Akira Takayama. Mathematical Economics. — New York : Cambridge University Press, 1985. — .
• Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2nd. — Springer, 2006. — .
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — .