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

Перейти к навигации Перейти к поиску

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

Условие Слейтера является примером условий регулярности^[2]. В частности, если условие Слейтера выполняется для прямой задачи, то разрыв двойственности равен 0 и, если значение двойственной задачи конечно, оно достигается^[3].

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

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

Минимизировать

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.\,

^[4].

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

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

Минимизировать

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

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

Литература

Morton Slater. Cowles Commission Discussion Paper No. 403. — 1950. Перепечатано в
- Traces and Emergence of Nonlinear Programming / Giorgio Giorgi, Tinne Hoff Kjeldsen. — Basel: Birkhäuser, 2014. — С. 293–306. — ISBN 978-3-0348-0438-7.
Akira Takayama. Mathematical Economics. — New York: Cambridge University Press, 1985. — ISBN 0-521-25707-7.
Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2nd. — Springer, 2006. — ISBN 0-387-29570-4.
Stephen Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — ISBN 978-0-521-83378-3.

Похожие исследовательские статьи

Лине́йное отображе́ние — обобщение линейной числовой функции на случай более общего множества аргументов и значений. Линейные отображения, в отличие от нелинейных, достаточно хорошо исследованы, что позволяет успешно применять результаты общей теории, так как их свойства не зависят от природы величин.

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах $\text{[math]}$ -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Важное свойство проективной плоскости — «симметрия» ролей, которые играют точки и прямые в определениях и теоремах, и двойственность является формализацией этой концепции. Имеются два подхода к концепции двойственности: один, использующий язык «принципа двойственности», позволяет объявить ряд теорем двойственными друг к другу, при этом двойственная к верной теореме тоже верна; и другой, функциональный подход, основанный на специальном отображении двойственности. Связь между подходами состоит в том, что двойственная теорема получается применением отображения двойственности к каждому объекту исходной. Возможен и координатный подход.

В теории оптимизации условия Каруша — Куна — Таккера — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.

Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.

Барьерная функция — непрерывная функция, значение которой в точке стремится к бесконечности при приближении точки к границе области допустимых решений.

Квадратичное программирование — это процесс решения задачи оптимизации специального типа, а именно — задачи оптимизации квадратичной функции нескольких переменных при линейных ограничениях на эти переменные. Квадратичное программирование является частным случаем нелинейного программирования.

Полуопределённое программирование — подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции на пересечении конусов положительно полуопределённых матриц с аффинным пространством.

Двойственность, или принцип двойственности, — принцип, по которому задачи оптимизации можно рассматривать с двух точек зрения, как прямую задачу или двойственную задачу. Решение двойственной задачи даёт нижнюю границу прямой задачи. Однако, в общем случае, значения целевых функций оптимальных решений прямой и двойственной задач не обязательно совпадают. Разница этих значений, если она наблюдается, называется разрывом двойственности. Для задач выпуклого программирования разрыв двойственности равен нулю при выполнении условий регулярности ограничений.

Сильная двойственность — это условие математической оптимизации, в котором оптимальные значения для прямой и двойственной задач равны. Это противоположно понятию слабой двойственности, когда прямая задача имеет оптимальное значение, не меньшее, чем у двойственной задачи, то есть разрыв двойственности больше либо равно нулю.

Разрыв двойственности — это разница между прямым и двойственным решениями. Если $\text{[math]}$ является оптимальным значением двойственной задачи, а $\text{[math]}$ является оптимальным значением прямой задачи, то разрыв двойственности равен $\text{[math]}$ . Это значение всегда больше либо равно нулю. Разрыв двойственности равен нулю тогда и только тогда, когда имеет место сильная двойственность. В противном случае разрыв строго положителен, и имеет место слабая двойственность.

Выпуклое программирование — это подобласть математической оптимизации, которая изучает задачу минимизации выпуклых функций на выпуклых множествах. В то время как многие классы задач выпуклого программирования допускают алгоритмы полиномиального времени, математическая оптимизация в общем случае NP-трудна.

Выпуклое сопряжение функции — это обобщение преобразования Лежандра, которое применяется к невыпуклым функциям. Оно известно также как преобразование Лежандра — Фенхеля или преобразование Фенхеля. Сопряжение используется для преобразования задачи оптимизации в соответствующую двойственную задачу, которую, возможно, проще решить.

Теорема Фенхеля — Моро — необходимое и достаточное условие того, что вещественнозначная функция равна своему двоекратному выпуклому сопряжению. При этом для любой функции верно, что $\text{[math]}$ .

Теорема двойственности Фенхеля — это результат в теории выпуклых функций, носящий имя немецкого математика Вернера Фенхеля.

Субградиентные методы — итеративные методы решения задач выпуклой минимизации. Субградиентные методы, разработанные Наумом Зуселевичем Шором сходятся, даже если применяются к недифференцируемым целевым функциям. Когда функция дифференцируема, субградиентные методы для задач без ограничений используют то же направление поиска, что и метод наискорейшего спуска.

<span class="mw-page-title-main">Выпуклый анализ</span>

Выпуклый анализ — это ветвь математики, посвящённая изучению свойств выпуклых функций и выпуклых множеств, часто имеющая приложения в выпуклом программировании, подобласти теории оптимизации.

Алгоритм Франк — Вульфа — это итеративный алгоритм оптимизации первого порядка для выпуклой оптимизации с ограничениями. Алгоритм известен также как метод условного градиента, метод приведённого градиента и алгоритм выпуклых комбинаций. Метод первоначально предложили Маргарита Франк и Филип Вульф в 1956. На каждой итерации алгоритм Франк — Вульфа рассматривает линейное приближение целевой функции и движется в направлении минимизации этой линейной функции.

Метод проксимального градиента — это обобщение проецирования, используемое для решения недифференцируемых задач выпуклого программирования.

Оптимизация с ограничениями — это процесс оптимизации целевой функции с учётом некоторых ограничений с некоторыми переменными. Целевая функция является функцией потерь, энергетической функцией, которая минимизируется, функцией вознаграждения, или функцией полезности, которая максимизируется.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.