最优化领域中,扰动函数(perturbation function)是与主问题和对偶问题相关的任何函数。由于任何此类函数都定义了对初始问题的扰动,所以叫做扰动函数。很多时候这种扰动的形式是约束的调整(shift)。[1]
有时值函数(value function)也被称作扰动函数,而扰动函数则称作双函数(bifunction)。[2]
给定豪斯多夫局部凸空间的两个对偶对
、
,以及函数
,可以定义主问题为
![{\displaystyle \inf _{x\in X}f(x).\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af409155447209aff8428ecad1fd0b9f1a753f0c)
可令
以将约束嵌入f,其中I是示性函数。则
是扰动函数,当且仅当
。[1][3]
在对偶性中的应用[编辑]
对偶间隙是不等式右式与左式之差
![{\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0db3abfa0b7e54ed9c3aa33a70fb60758439e7d5)
其中
是两个变量的凸共轭。[3][4]
对扰动函数F的任意选择,弱对偶都成立。有一些条件一旦满足,就意味着强对偶。[3]例如,若F是下半连续的真联合凸函数,且
(其中
是代数内部,
是由
定义的到Y的投影),并且X、Y是弗雷歇空间,则强对偶性成立。[1]
拉格朗日量[编辑]
令
、
对偶(为对偶对)。给定主问题(最小化
)与相关的扰动函数(
),则拉格朗日量
是F关于y的负共轭(即凸共轭),也就是说拉格朗日量的定义是
![{\displaystyle L(x,y^{*})=\inf _{y\in Y}\left\{F(x,y)-y^{*}(y)\right\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/363a71be19bdf1dc53acb6b7a80dc804f5986260)
特别地,弱对偶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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79cbd18e7ebe992a46d396ee04892ee66a377f07)
若主问题是
![{\displaystyle \inf _{x:g(x)\leq 0}f(x)=\inf _{x\in X}{\tilde {f}}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0e0fe6cb890c13c0924ebca97e2797ac848b85a)
其中
。则若扰动是
![{\displaystyle \inf _{x:g(x)\leq y}f(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebb906922f9368decfa8a9e247dde7c3138fd473)
则扰动函数是
![{\displaystyle F(x,y)=f(x)+I_{\mathbb {R} _{+}^{d}}(y-g(x)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34b3c5f1822f6ed9cbe4a762243ea6605279caaf)
于是,可见与拉格朗日对偶的联系,因为L可以简单地看成是
![{\displaystyle L(x,y^{*})={\begin{cases}f(x)-y^{*}(g(x))&{\text{if }}y^{*}\in \mathbb {R} _{-}^{d},\\-\infty &{\text{else}}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a006bf8c636d5e50e2a744b5615a06b3eef950f5)
芬切尔对偶性[编辑]
令
、
对偶。假定存在线性映射
与伴随算子
。假定主目标函数
(通过示性函数,包含了约束)可以写作
使得
,则扰动函数为
![{\displaystyle F(x,y)=J(x,Tx-y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f9755ce8d9c3d7a1b13caed3bf42e7982a56591)
特别地,若主目标函数是
,则扰动函数来自
,这是芬切尔对偶性的传统定义。[5]
参考文献[编辑]
- ^ 1.0 1.1 1.2 Radu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad. Duality in Vector Optimization. Springer. 2009. ISBN 978-3-642-02885-4.
- ^ J. P. Ponstein. Approaches to the Theory of Optimization. Cambridge University Press. 2004. ISBN 978-0-521-60491-8.
- ^ 3.0 3.1 3.2 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.
- ^ 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.
- ^ Radu Ioan Boţ. Conjugate Duality in Convex Optimization. Springer. 2010: 68. ISBN 978-3-642-04899-9.