Меню Главная Случайная статья Настройки Условие Слейтера Материал из https://ru.wikipedia.org Условие Слейтера — это достаточное условие для строгой двойственности в задаче выпуклой оптимизации. Условие названо именем Мортона Л. Слейтера[1]. Неформально условие Слейтера утверждает, что допустимая область должна иметь внутреннюю точку (см. подробности ниже). Условие Слейтера является примером условий регулярности[2]. В частности, если условие Слейтера выполняется для прямой задачи, то разрыв двойственности равен 0 и, если значение двойственной задачи конечно, оно достигается[3]. Содержание 1 Формулировка 2 Обобщённые неравенства 3 Примечания 4 Литература Формулировка Рассмотрим задачу оптимизации Минимизировать ${\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]. Примечания Slater, 1950. Takayama, 1985, с. 66–76. Borwein, Lewis, 2006. 1 2 Boyd, Vandenberghe, 2004. Литература Morton Slater. Cowles Commission Discussion Paper No. 403. — 1950. Перепечатано в Traces and Emergence of Nonlinear Programming / Giorgio Giorgi, Tinne Hoff Kjeldsen. — Basel: Birkhuser, 2014. — С. 293–306. — ISBN 978-3-0348-0438-7.