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

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

Условие Слейтера является примером условий регулярностиШаблон:Sfn. В частности, если условие Слейтера выполняется для прямой задачи, то разрыв двойственности равен 0 и, если значение двойственной задачи конечно, оно достигаетсяШаблон:Sfn.

Формулировка

Рассмотрим задачу оптимизации

Минимизировать $f_0(x)$

При ограничениях

$f_i(x)⩽0,i=1,\dots ,m$

$Ax=b$,

где $f_0,\dots ,f_m$ являются выпуклыми функциями. Это экземпляр задачи выпуклого программирования.

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

Математически условие Слейтера утверждает, что сильная двойственность выполняется, если существует точка $x^{*}\in \mathrm{relint}(D)$ (где relint обозначает относительную внутренность выпуклого множества $D:=\underset{i=0}{\overset{m}{\cap }}\mathrm{dom}(f_i)$), такая, что

$f_i(x^{*})<0,i=1,\dots ,m,$ (выпуклые нелинейные ограничения)

$A{x}^{*}=b.$Шаблон:Sfn.

Обобщённые неравенства

Пусть дана задача

Минимизировать $f_0(x)$

При ограничениях

$f_i(x){⩽}_{K_i}0,i=1,\dots ,m$

$Ax=b$,

где функция $f_0$ выпукла, а $f_i$ $K_i$-выпукла для любого $i$. Тогда условие Слейтера гласит, что в случае, когда существует $x^{*}\in \mathrm{relint}(D)$, такое, что

$f_i(x^{*}){<}_{K_i}0,i=1,\dots ,m$ и

$A{x}^{*}=b$

то имеет место строгая двойственностьШаблон:Sfn.

Литература

• Шаблон:Статья Перепечатано в
  • Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга