Функция возмущения

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

В некоторых текстах функцию цены называют функцией возмущения, а функцию возмущения называют бифункцией . ^[2]

Определение

Даны две двойственные пары разделенных . локально выпуклых пространств $\left(X,X^{*}\right)$ и $\left(Y,Y^{*}\right)$ . Тогда, учитывая функцию $f:X\to \mathbb {R} \cup \{+\infty \}$ , мы можем определить основную проблему как

\inf _{x\in X}f(x).\,

Если существуют условия ограничения, их можно встроить в функцию $f$ позволяя $f\leftarrow f+I_{\mathrm {constraints} }$ где $I$ – характеристическая функция . Затем $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ является функцией возмущения тогда и только тогда, когда $F(x,0)=f(x)$ . ^[1]^[3]

Использование в дуальности

— Разрыв двойственности это разница правой и левой части неравенства.

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),

где $F^{*}$ является выпуклым сопряжением по обеим переменным. ^[3]^[4]

При любом выборе функции возмущения F имеет место слабая двойственность . Существует ряд условий, выполнение которых подразумевает сильную двойственность . ^[3] Например, если F собственная , совместно выпуклая , полунепрерывная снизу с $0\in \operatorname {core} ({\Pr }_{Y}(\operatorname {dom} F))$ (где $\operatorname {core}$ является алгебраической внутренностью и ${\Pr }_{Y}$ — это проекция на Y, определяемая формулой ${\Pr }_{Y}(x,y)=y$ ) и X , Y — пространства Фреше , то имеет место сильная двойственность. ^[1]

Примеры

лагранжиан

Позволять $(X,X^{*})$ и $(Y,Y^{*})$ быть двойственными парами. Учитывая основную задачу (минимизировать f ( x )) и связанную с ней функцию возмущения ( F ( x , y )) тогда лагранжиан $L:X\times Y^{*}\to \mathbb {R} \cup \{+\infty \}$ является отрицательным сопряжением F относительно y (т.е. вогнутым сопряжением). То есть лагранжиан определяется формулой

L(x,y^{*})=\inf _{y\in Y}\left\{F(x,y)-y^{*}(y)\right\}.

В частности, слабой двойственности можно показать, что уравнение minmax имеет вид

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})=\sup _{y^{*}\in Y^{*}}\inf _{x\in X}L(x,y^{*})\leq \inf _{x\in X}\sup _{y^{*}\in Y^{*}}L(x,y^{*})=\inf _{x\in X}F(x,0).

Если основная проблема задана формулой

\inf _{x:g(x)\leq 0}f(x)=\inf _{x\in X}{\tilde {f}}(x)

где ${\tilde {f}}(x)=f(x)+I_{\mathbb {R} _{+}^{d}}(-g(x))$ . Тогда, если возмущение определяется выражением

\inf _{x:g(x)\leq y}f(x)

тогда функция возмущения равна

F(x,y)=f(x)+I_{\mathbb {R} _{+}^{d}}(y-g(x)).

Таким образом, можно увидеть связь с лагранжевой двойственностью, поскольку L можно тривиально увидеть как

L(x,y^{*})={\begin{cases}f(x)-y^{*}(g(x))&{\text{if }}y^{*}\in \mathbb {R} _{-}^{d},\\-\infty &{\text{else}}.\end{cases}}

Двойственность Фенхеля

Позволять $(X,X^{*})$ и $(Y,Y^{*})$ быть двойственными парами. Предположим, что существует линейное отображение $T:X\to Y$ с присоединенным оператором $T^{*}:Y^{*}\to X^{*}$ . Предположим, что основная целевая функция $f(x)$ (включая ограничения посредством индикаторной функции) можно записать как $f(x)=J(x,Tx)$ такой, что $J:X\times Y\to \mathbb {R} \cup \{+\infty \}$ . Тогда функция возмущения имеет вид

F(x,y)=J(x,Tx-y).

В частности, если основной целью является $f(x)+g(Tx)$ тогда функция возмущения имеет вид $F(x,y)=f(x)+g(Tx-y)$ , что является традиционным определением дуальности Фенхеля . ^[5]

Ссылки

^ Jump up to: ^а ^б ^с Раду Йоан Бот; Герт Ванка; Сорин-Михай Град (2009). Двойственность в векторной оптимизации . Спрингер. ISBN 978-3-642-02885-4 .
^ Дж. П. Понштейн (2004). Подходы к теории оптимизации . Издательство Кембриджского университета. ISBN 978-0-521-60491-8 .
^ Jump up to: ^а ^б ^с Залинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., Inc., стр. 106–113. ISBN 981-238-067-1 . МР 1921556 .
^ Эрно Роберт Четнек (2010). Преодоление несостоятельности классических обобщенных условий регулярности внутренних точек в выпуклой оптимизации. Приложения теории двойственности к расширениям максимальных монотонных операторов . Логотипы Верлаг Берлин ГмбХ. ISBN 978-3-8325-2503-3 .
^ Раду Иоан Бот (2010). Сопряженная двойственность в выпуклой оптимизации . Спрингер. п. 68. ИСБН 978-3-642-04899-9 .

[BWG-1] Jump up to: ^а ^б ^с Раду Йоан Бот; Герт Ванка; Сорин-Михай Град (2009). Двойственность в векторной оптимизации . Спрингер. ISBN 978-3-642-02885-4 .

[2] Дж. П. Понштейн (2004). Подходы к теории оптимизации . Издательство Кембриджского университета. ISBN 978-0-521-60491-8 .

[Zalinescu-3] Jump up to: ^а ^б ^с Залинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., Inc., стр. 106–113. ISBN 981-238-067-1 . МР 1921556 .

[4] Эрно Роберт Четнек (2010). Преодоление несостоятельности классических обобщенных условий регулярности внутренних точек в выпуклой оптимизации. Приложения теории двойственности к расширениям максимальных монотонных операторов . Логотипы Верлаг Берлин ГмбХ. ISBN 978-3-8325-2503-3 .

[5] Раду Иоан Бот (2010). Сопряженная двойственность в выпуклой оптимизации . Спрингер. п. 68. ИСБН 978-3-642-04899-9 .

[1]

[2]

[3]

[4]

[5]