Función de perturbación

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

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

Definición

Dados dos pares duales separados localmente con espacios convexos y . Entonces, dada la función , podemos definir el problema primario por${\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 dejando dónde está 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 del 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 una fuerte dualidad . ^[3] Por ejemplo, si F es propio , conjuntamente convexo , semicontinuo 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 mantiene 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 de

Lagrangiano

Sean y sean pares duales. Dado un problema primario (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 ay (es decir, el conjugado cóncavo). Que es 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 primario viene dado por

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

donde . Entonces, si la perturbación viene 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)).}$

Por lo tanto, 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 fenchel

Artículo principal: dualidad Fenchel

Sean y sean pares duales. Suponga que existe un mapa lineal con un operador adjunto . Suponga que la función objetivo principal (incluidas las restricciones mediante la función de indicador) se puede escribir como tal que . Entonces la función de perturbación viene 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 viene 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 la optimización vectorial . Saltador. ISBN 978-3-642-02885-4.
2. JP Ponstein (2004). Aproximaciones a la teoría de la optimización . Prensa de la Universidad de Cambridge. ISBN 978-0-521-60491-8.
3. Zălinescu, C. (2002). Análisis convexo en espacios vectoriales generales . River Edge, Nueva Jersey: World Scientific Publishing Co., Inc. págs. 106-113. ISBN 981-238-067-1. Señor  1921556 .
4. Ernö Robert Csetnek (2010). Superar el fracaso de las condiciones clásicas de regularidad generalizada del punto interior en la optimización convexa. Aplicaciones de la teoría de la 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 . Saltador. pag. 68. ISBN 978-3-642-04899-9.