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

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

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

Примечания

Литература