В математической оптимизации , то функция возмущения является любой функцией , которая относится к прямым и двойственным задачам . Название происходит от того факта, что любая такая функция определяет возмущение исходной задачи. Во многих случаях это принимает форму смещения ограничений. [1]
В некоторых текстах функция цены называется функцией возмущения, а функция возмущения - бифункцией . [2]
Определение
Даны две двойственные пары, разделенные локально выпуклыми пространствами а также . Тогда с учетом функции, мы можем определить основную задачу как
Если есть условия ограничения, их можно встроить в функцию позволяя где - характеристическая функция . потомявляется возмущающей функцией тогда и только тогда, когда. [1] [3]
Использование в дуальности
Разрыв двойственности является разность правой и левой части неравенства
где является выпуклым сопряженным по обеим переменным. [3] [4]
При любом выборе возмущающей функции F имеет место слабая двойственность . Есть ряд условий, выполнение которых подразумевает сильную двойственность . [3] Например, если Р является правильным , совместно выпуклым , полунепрерывным снизу с (где - алгебраическая внутренность иявляется проекцией на Y определяется) и X , Y - пространства Фреше, то имеет место сильная двойственность. [1]
Примеры
Лагранжиан
Позволять а также быть двойственными парами. Для прямой задачи (минимизировать f ( x )) и связанной с ней функции возмущения ( F ( x , y )) лагранжиан - отрицательное сопряжение F относительно y (т. е. вогнутое сопряжение). То есть лагранжиан определяется как
В частности, можно показать, что уравнение слабой двойственности minmax имеет вид
Если основная проблема задается
где . Тогда, если возмущение дается выражением
то функция возмущения
Таким образом, можно увидеть связь с лагранжевой двойственностью, поскольку L тривиально можно увидеть как
Двойственность фенхеля
Позволять а также быть двойственными парами. Предположим, что существует линейное отображение с сопряженным оператором . Предположим, что основная целевая функция (включая ограничения посредством индикаторной функции) можно записать как такой, что . Тогда функция возмущения определяется выражением
В частности, если основная цель тогда функция возмущения задается выражением , что является традиционным определением двойственности Фенхеля . [5]
Рекомендации
- ^ a b c Раду Иоан Бо; Герт Ванка; Сорин-Михай Град (2009). Двойственность в векторной оптимизации . Springer. ISBN 978-3-642-02885-4.
- ^ JP Ponstein (2004). Подходы к теории оптимизации . Издательство Кембриджского университета. ISBN 978-0-521-60491-8.
- ^ а б в Зэлинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., Inc., стр. 106–113. ISBN 981-238-067-1. Руководство по ремонту 1921556 .
- ^ Эрнё Роберт Четнек (2010). Преодоление несоблюдения классических обобщенных условий регулярности внутренней точки при выпуклой оптимизации. Приложения теории двойственности к расширению максимальных монотонных операторов . Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.
- ^ Раду Иоан Бо (2010). Сопряженная двойственность в выпуклой оптимизации . Springer. п. 68. ISBN 978-3-642-04899-9.