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

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

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

Определение

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

${\ Displaystyle \ Inf _ {х \ в X} е (х). \,}$

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

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

Разрыв двойственности является разность правой и левой части неравенства

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

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

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

Примеры

Лагранжиан

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

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

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

${\ 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).}$

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

${\ Displaystyle \ Inf _ {х: г (х) \ Leq 0} е (х) = \ inf _ {х \ in X} {\ тильда {f}} (х)}$

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

${\ Displaystyle \ Inf _ {х: г (х) \ Leq у} е (х)}$

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

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

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

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

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

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

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

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

Ссылки