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

редактировать

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

В некоторых текстах функция значения называется функцией возмущения, а функция возмущения - бифункцией .

Содержание

1 Определение
2 Использование в двойственности
3 Примеры
- 3.1 Лагранжиан
- 3.2 Двойственность Фенхеля
4 Ссылки

Определение

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

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

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

Если есть условия ограничения, они могут быть встроены в функцию $f {\ displaystyle f}$ $f$ разрешив $f ← f + I ограничениям {\ displaystyle f \ leftarrow f + I _ {\ mathrm {constraints}}}$ ${\ displaystyle f \ leftarrow f + I _ {\ mathrm {constraints}}}$ где $I {\ displaystyle I}$ $I$ - характеристическая функция. Тогда $F: X × Y → R ∪ {+ ∞} {\ displaystyle F: X \ times Y \ to \ mathbb {R} \ cup \ {+ \ infty \}}$ $F: X \ times Y \ to \ mathbb {R} \ cup \ {+ \ infty \}$ является функция возмущения тогда и только тогда, когда $F (x, 0) = f (x) {\ displaystyle F (x, 0) = f (x)}$ $F(x,0)=f(x)$ .

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

The разрыв двойственности - это разность правой и левой части неравенства

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

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

где $F ∗ {\ displaystyle F ^ {*}}$ $F ^ {*}$ - это выпуклое сопряжение в обеих переменных.

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

Примеры

Лагранжиан

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

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

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

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

sup y ∗ ∈ Y ∗ - F ∗ (0, y ∗) = sup y ∗ ∈ Y ∗ inf x ∈ XL (x, y ∗) ≤ inf x ∈ X sup y ∗ ∈ Y ∗ L (x, y ∗) = inf x ∈ XF (x, 0). {\ displaystyle \ 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).}

\ 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) ≤ 0 е (Икс) знак равно Inf Икс ∈ Икс е ~ (Икс) {\ Displaystyle \ Inf _ {х: г (х) \ Leq 0} F (х) = \ Inf _ {х \ в X} {\ тильда {е }} (x)}

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

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

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

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

, то возмущение функция

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

{\ displaystyle F (x, y) = f (x) + I _ {\ mathbb { R} _ {+} ^ {d}} (yg (x)).}

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

L (x, y ∗) = {f (x) + y ∗ (g (x)), если y ∗ ∈ R + d, - ∞ иначе. {\ displaystyle L (x, y ^ {*}) = {\ begin {case} f (x) + y ^ {*} (g (x)) {\ text {if}} y ^ {*} \ в \ mathbb {R} _ {+} ^ {d}, \\ - \ infty {\ text {else}}. \ end {cases}}}

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

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

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

F (x, y) = J (x, T x - y). {\ Displaystyle F (x, y) = J (x, Tx-y).}

{\ Displaystyle F (x, y) = J (x, Tx-y).}

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

Ссылки