查看“︁扰动函数”︁的源代码

[[最优化]]领域中，'''扰动函数'''（perturbation function）是与主问题和[[对偶问题]]相关的任何[[函数]]。由于任何此类函数都定义了对初始问题的扰动，所以叫做扰动函数。很多时候这种扰动的形式是约束的调整（shift）。<ref name="BWG">{{cite book|title=Duality in Vector Optimization|author1=Radu Ioan Boţ|author2=Gert Wanka|author3=Sorin-Mihai Grad|year=2009|publisher=Springer|isbn=978-3-642-02885-4}}</ref>

有时[[值函数]]（value function）也被称作扰动函数，而扰动函数则称作'''双函数'''（bifunction）。<ref>{{cite book|title=Approaches to the Theory of Optimization|url=https://archive.org/details/approachestotheo0000jppo|author=J. P. Ponstein|publisher=Cambridge University Press|year=2004|isbn=978-0-521-60491-8}}</ref>

== 定义 ==
给定[[豪斯多夫空间|豪斯多夫]][[局部凸拓扑向量空间|局部凸空间]]的两个[[对偶对]]<math>\left(X,X^*\right)</math>、<math>\left(Y,Y^*\right)</math>，以及函数<math>f: X \to \mathbb{R} \cup \{+\infty\}</math>，可以定义主问题为

:<math>\inf_{x \in X} f(x). \, </math>

可令<math>f \leftarrow f + I_\mathrm{constraints}</math>以将约束嵌入''f''，其中''I''是[[示性函数 (凸分析)|示性函数]]。则<math>F: X \times Y \to \mathbb{R} \cup \{+\infty\}</math>是扰动函数，当且仅当<math>F(x,0) = f(x)</math>。<ref name="BWG" /><ref name="Zalinescu">{{cite book|last=Zălinescu|first=C.|title=Convex analysis in general vector spaces|publisher=World Scientific Publishing&nbsp; Co.,&nbsp;Inc|location = River Edge,&nbsp;NJ |year=2002|pages=106–113|isbn=981-238-067-1|mr=1921556}}</ref>

== 在对偶性中的应用 ==
[[对偶间隙]]是不等式右式与左式之差
:<math>\sup_{y^* \in Y^*} -F^*(0,y^*) \le \inf_{x \in X} F(x,0),</math>
其中<math>F^*</math>是两个变量的[[凸共轭]]。<ref name="Zalinescu" /><ref>{{cite book|title=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|author=Ernö Robert Csetnek|year=2010|publisher=Logos Verlag Berlin GmbH|isbn=978-3-8325-2503-3}}</ref>

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

== 例子 ==
=== 拉格朗日量 ===
令<math>(X,X^*)</math>、<math>(Y,Y^*)</math>对偶（为对偶对）。给定主问题（最小化<math>f(x)</math>）与相关的扰动函数（<math>F(x,\ y)</math>），则'''拉格朗日量'''<math>L: X \times Y^* \to \mathbb{R} \cup \{+\infty\}</math>是''F''关于''y''的负共轭（即凸共轭），也就是说拉格朗日量的定义是
:<math>L(x,y^*) = \inf_{y \in Y} \left\{F(x,y) - y^*(y)\right\}.</math>
特别地，[[弱对偶]]minmax方程可以证明为
:<math>\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).</math>

若主问题是
:<math>\inf_{x: g(x) \leq 0} f(x) = \inf_{x \in X} \tilde{f}(x)</math>
其中<math>\tilde{f}(x) = f(x) + I_{\mathbb{R}^d_+}(-g(x))</math>。则若扰动是
:<math>\inf_{x: g(x) \leq y} f(x)</math>
则扰动函数是
:<math>F(x,y) = f(x) + I_{\mathbb{R}^d_+}(y - g(x)).</math>
于是，可见与拉格朗日对偶的联系，因为''L''可以简单地看成是
:<math>L(x,y^*) = \begin{cases} 
 f(x) - y^*(g(x)) & \text{if } y^* \in \mathbb{R}^d_-, \\
 -\infty & \text{else}.
\end{cases}</math>

=== 芬切尔对偶性 ===
{{main|芬切尔对偶性}}
令<math>(X,X^*)</math>、<math>(Y,Y^*)</math>对偶。假定存在[[线性映射]]<math>T: X \to Y</math>与[[厄米伴随|伴随算子]]<math>T^*: Y^* \to X^*</math>。假定主目标函数<math>f(x)</math>（通过示性函数，包含了约束）可以写作<math>f(x) = J(x,Tx)</math>使得<math>J: X \times Y \to \mathbb{R} \cup \{+\infty\}</math>，则扰动函数为
: <math>F(x,y) = J(x,Tx - y).</math>

特别地，若主目标函数是<math>f(x) + g(Tx)</math>，则扰动函数来自<math>F(x,y) = f(x) + g(Tx - y)</math>，这是[[芬切尔对偶性]]的传统定义。<ref>{{cite book|title=Conjugate Duality in Convex Optimization|author=Radu Ioan Boţ|publisher=Springer|year=2010|isbn=978-3-642-04899-9|page=68}}</ref>

== 参考文献 ==
{{Reflist}}

[[Category:线性规划]]
[[Category:凸优化]]