擾動函數

最優化領域中，擾動函數（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]

參考文獻

1. Radu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad. Duality in Vector Optimization. Springer. 2009. ISBN 978-3-642-02885-4.
2. J. P. Ponstein. Approaches to the Theory of Optimization. Cambridge University Press. 2004. ISBN 978-0-521-60491-8.
3. Zălinescu, C. Convex analysis in general vector spaces. River Edge, NJ: World Scientific Publishing  Co., Inc. 2002: 106–113. ISBN 981-238-067-1. MR 1921556.
4. Ernö Robert Csetnek. Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Logos Verlag Berlin GmbH. 2010. ISBN 978-3-8325-2503-3.
5. Radu Ioan Boţ. Conjugate Duality in Convex Optimization. Springer. 2010: 68. ISBN 978-3-642-04899-9.