扰动函数

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

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

定义

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

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

可令$f\leftarrow f+I_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{s}}$以将约束嵌入f，其中I是示性函数。则$F:X\times Y\to ℝ\cup \{+\mathrm{\infty }\}$是扰动函数，当且仅当$F(x,0)=f(x)$。

在对偶性中的应用

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

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

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

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

例子

拉格朗日量

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

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

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

$\underset{y^{*}\in Y^{*}}{\sup }-F^{*}(0,y^{*})=\underset{y^{*}\in Y^{*}}{\sup }\underset{x\in X}{\inf }L(x,y^{*})\le \underset{x\in X}{\inf }\underset{y^{*}\in Y^{*}}{\sup }L(x,y^{*})=\underset{x\in X}{\inf }F(x,0).$

若主问题是

$\underset{x:g(x)\le 0}{\inf }f(x)=\underset{x\in X}{\inf }\tilde{f}(x)$

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

$\underset{x:g(x)\le y}{\inf }f(x)$

则扰动函数是

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

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

$L(x,y^{*})=\{\begin{array}{cc}f(x)-y^{*}(g(x))& \text{if }{y}^{*}\in {ℝ}_{-}^d,\\ -\mathrm{\infty }& \text{else}.\end{array}$

芬切尔对偶性

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

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

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