Условие Слейтера

Условие Слейтера — это достаточное условие для строгой двойственности в задаче выпуклой оптимизации. Условие названо именем Мортона Л. Слейтера. Неформально условие Слейтера утверждает, что допустимая область должна иметь внутреннюю точку (см. подробности ниже).

Условие Слейтера является примером условий регулярности. В частности, если условие Слейтера выполняется для прямой задачи, то разрыв двойственности равен 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$

то имеет место строгая двойственность.