Función de perturbación

En optimización matemática , la función de perturbación es cualquier función relacionada con problemas primarios y duales . El nombre proviene del hecho de que cualquier función de este tipo define una perturbación del problema inicial. En muchos casos, esto toma la forma de un desplazamiento de las restricciones. ^[1]

En algunos textos la función de valor se denomina función de perturbación, y la función de perturbación se denomina bifunción . ^[2]

Definición

Dados dos pares duales de espacios localmente convexos separados y . Entonces, dada la función , podemos definir el problema primal mediante ${\displaystyle \left(X,X^{*}\right)}$ ${\displaystyle \left(Y,Y^{*}\right)}$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$

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

Si existen condiciones de restricción, estas se pueden incorporar a la función haciendo que donde es la función característica . Entonces es una función de perturbación si y solo si . ^{[1] [3]} ${\displaystyle f}$ ${\displaystyle f\leftarrow f+I_{\mathrm {constraints} }}$ ${\displaystyle I}$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ ${\displaystyle F(x,0)=f(x)}$

Uso en dualidad

La brecha de dualidad es la diferencia entre el lado derecho e izquierdo de la desigualdad.

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

donde es el conjugado convexo en ambas variables. ^{[3] [4]} ${\displaystyle F^{*}}$

Para cualquier elección de función de perturbación F se cumple la dualidad débil . Hay una serie de condiciones que, si se cumplen, implican dualidad fuerte . ^[3] Por ejemplo, si F es propia , conjuntamente convexa , semicontinua inferior con (donde es el interior algebraico y es la proyección sobre Y definida por ) y X , Y son espacios de Fréchet , entonces se cumple la dualidad fuerte. ^[1] ${\displaystyle 0\in \operatorname {core} ({\Pr }_{Y}(\operatorname {dom} F))}$ ${\displaystyle \operatorname {core} }$ ${\displaystyle {\Pr }_{Y}}$ ${\displaystyle {\Pr }_{Y}(x,y)=y}$

Ejemplos

Lagrangiano

Sean y pares duales. Dado un problema primal (minimizar f ( x )) y una función de perturbación relacionada ( F ( x , y )), entonces el lagrangiano es el conjugado negativo de F con respecto a y (es decir, el conjugado cóncavo). Es decir, el lagrangiano se define por ${\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\}.}$

En particular, se puede demostrar que la ecuación minmax de dualidad débil es

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

Si el problema primal está dado por

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

donde . Entonces, si la perturbación está dada por ${\displaystyle {\tilde {f}}(x)=f(x)+I_{\mathbb {R} _{+}^{d}}(-g(x))}$

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

entonces la función de perturbación es

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

De esta manera se puede ver la conexión con la dualidad lagrangiana, ya que se puede ver trivialmente que L es

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

Dualidad de Fenchel

Sean y pares duales. Supongamos que existe una función lineal con operador adjunto . Supongamos que la función objetivo primaria (incluidas las restricciones por medio de la función indicadora) se puede escribir como tal que . Entonces la función de perturbación está dada por ${\displaystyle (X,X^{*})}$ ${\displaystyle (Y,Y^{*})}$ ${\displaystyle T:X\to Y}$ ${\displaystyle T^{*}:Y^{*}\to X^{*}}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)=J(x,Tx)}$ ${\displaystyle J:X\times Y\to \mathbb {R} \cup \{+\infty \}}$

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

En particular, si el objetivo primordial es entonces la función de perturbación está dada por , que es la definición tradicional de la dualidad de Fenchel . ^[5] ${\displaystyle f(x)+g(Tx)}$ ${\displaystyle F(x,y)=f(x)+g(Tx-y)}$

Referencias

1. Radu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad (2009). Dualidad en optimización vectorial . Springer. ISBN 978-3-642-02885-4.
2. JP Ponstein (2004). Enfoques de la teoría de la optimización . Cambridge University Press. ISBN 978-0-521-60491-8.
3. Zălinescu, C. (2002). Análisis convexo en espacios vectoriales generales . River Edge, NJ: World Scientific Publishing Co., Inc., págs. 106-113. ISBN 981-238-067-1.Señor 1921556  .
4. Ernö Robert Csetnek (2010). Superando el fracaso de las condiciones clásicas de regularidad generalizada de punto interior en la optimización convexa. Aplicaciones de la teoría de dualidad a ampliaciones de operadores monótonos máximos . Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.
5. Radu Ioan Boţ (2010). Dualidad conjugada en optimización convexa . Springer. pág. 68. ISBN 978-3-642-04899-9.