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]

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)}$

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}$

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}}}$

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)}$