擾動函數

最優化領域中，擾動函數（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)$，這是芬切爾對偶性的傳統定義。