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

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

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

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

Розглянемо задачу оптимізації: Мінімізувати ${\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}$^[4].

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

Нехай дано задачу: Мінімізувати ${\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,}$

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