扰动函数

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

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

定义

给定豪斯多夫局部凸空间的两个对偶对${\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).\,}$

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

在对偶性中的应用

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

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

其中${\displaystyle F^{*}}$是两个变量的凸共轭。^[3][4]

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

例子

拉格朗日量

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

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

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

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

若主问题是

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

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

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

则扰动函数是

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

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

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

芬切尔对偶性

主条目：芬切尔对偶性

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

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