扰动函数

最优化领域中，扰动函数（perturbation function）是与主问题和对偶问题相关的任何函数。由于任何此类函数都定义了对初始问题的扰动，所以叫做扰动函数。很多时候这种扰动的形式是约束的调整（shift）。

有时值函数（value function）也被称作扰动函数，而扰动函数则称作双函数（bifunction）。

定义

给定豪斯多夫局部凸空间的两个对偶对$\left(X,X^{*}\right)$、$\left(Y,Y^{*}\right)$，以及函数$f:X\to \mathbb {R} \cup \{+\infty \}$，可以定义主问题为

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

可令$f\leftarrow f+I_{\mathrm {constraints} }$以将约束嵌入f，其中I是示性函数。则$F:X\times Y\to \mathbb {R} \cup \{+\infty \}$是扰动函数，当且仅当$F(x,0)=f(x)$。

在对偶性中的应用

对偶间隙是不等式右式与左式之差

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

其中$F^{*}$是两个变量的凸共轭。

对扰动函数F的任意选择，弱对偶都成立。有一些条件一旦满足，就意味着强对偶。例如，若F是下半连续的真联合凸函数，且$0\in \operatorname {core} ({\Pr }_{Y}(\operatorname {dom} F))$（其中$\operatorname {core}$是代数内部，${\Pr }_{Y}$是由${\Pr }_{Y}(x,y)=y$定义的到Y的投影），并且X、Y是弗雷歇空间，则强对偶性成立。

例子

拉格朗日量

令$(X,X^{*})$、$(Y,Y^{*})$对偶（为对偶对）。给定主问题（最小化$f(x)$）与相关的扰动函数（$F(x,\ y)$），则拉格朗日量$L:X\times Y^{*}\to \mathbb {R} \cup \{+\infty \}$是F关于y的负共轭（即凸共轭），也就是说拉格朗日量的定义是

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

特别地，弱对偶minmax方程可以证明为

$\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)\leq 0}f(x)=\inf _{x\in X}{\tilde {f}}(x)$

其中${\tilde {f}}(x)=f(x)+I_{\mathbb {R} _{+}^{d}}(-g(x))$。则若扰动是

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

则扰动函数是

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

于是，可见与拉格朗日对偶的联系，因为L可以简单地看成是

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

芬切尔对偶性

主条目：芬切尔对偶性

令$(X,X^{*})$、$(Y,Y^{*})$对偶。假定存在线性映射$T:X\to Y$与伴随算子$T^{*}:Y^{*}\to X^{*}$。假定主目标函数$f(x)$（通过示性函数，包含了约束）可以写作$f(x)=J(x,Tx)$使得$J:X\times Y\to \mathbb {R} \cup \{+\infty \}$，则扰动函数为

$F(x,y)=J(x,Tx-y).$

特别地，若主目标函数是$f(x)+g(Tx)$，则扰动函数来自$F(x,y)=f(x)+g(Tx-y)$，这是芬切尔对偶性的传统定义。