摂動函数

数学の数理最適化の分野において、摂動函数（せつどうかんすう、英: perturbation function）とは、主問題と双対問題を関連づける任意の函数である。そのような任意の函数は元の問題の摂動を定義する事実から、その名が付けられた。多くの場合、この函数は制約条件をシフトする形状を取る^[1]。

文献によっては、価値函数（英語版）が摂動函数と呼ばれ、摂動函数は二重函数（bifunction）と呼ばれることもある^[2]。

定義

分離的な局所凸空間の二つの双対組 ${\displaystyle \left(X,X^{*}\right)}$ と ${\displaystyle \left(Y,Y^{*}\right)}$ が与えられるとする。このとき、与えられた函数 ${\displaystyle f\colon X\to \mathbb {R} \cup \{+\infty \}}$ に対する主問題を次で定義する。

${\displaystyle \inf _{x\in X}f(x).\,}$

制約条件が存在するならば、それら制約条件を ${\displaystyle f=f+I_{\text{constraints}}}$ として函数 ${\displaystyle f}$ に含めてしまうこともできる。ここで ${\displaystyle 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} (\operatorname {Pr} _{Y}(\operatorname {dom} F))}$ であり（ここで ${\displaystyle \operatorname {core} }$ は代数的内部を表し、${\displaystyle \operatorname {Pr} _{Y}}$ は ${\displaystyle \operatorname {Pr} _{Y}(x,y)=y}$ で定義される Y の上への射影である）、X と Y がフレシェ空間であるなら、強双対性は成立する^[1]。

例

ラグランジアン

${\displaystyle (X,X^{*})}$ と ${\displaystyle (Y,Y^{*})}$ を双対組とする。（f(x) を最小化する）主問題と、関連する摂動函数 (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\}.}$

特に、弱双対ミニマックス方程式は次のように表される。

${\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 {\tilde {f}}(x)=f(x)+I_{\mathbb {R} _{+}^{d}}(-g(x))}$ に対し

${\displaystyle \inf _{x:g(x)\leq 0}f(x)=\inf _{x\in X}{\tilde {f}}(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 J:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ に対して ${\displaystyle f(x)=J(x,Tx)}$ と表すことが出来るものとする。このとき、摂動函数は次で与えられる。

${\displaystyle F(x,y)=J(x,Tx-y)}$.

特に、主目的函数が ${\displaystyle f(x)+g(Tx)}$ であるなら、摂動函数は ${\displaystyle F(x,y)=f(x)+g(Tx-y)}$ で与えられるが、これはフェンシェル双対性の伝統的な定義である^[5]。