最優化領域中,擾動函數(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]
參考文獻