摂動函数

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

文献によっては、テンプレート:仮リンクが摂動函数と呼ばれ、摂動函数は二重函数（bifunction）と呼ばれることもある。

定義

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

$\underset{x\in X}{\inf }f(x).$

制約条件が存在するならば、それら制約条件を $f=f+I_{\text{constraints}}$ として函数 $f$ に含めてしまうこともできる。ここで $I$ はテンプレート:仮リンクである。このとき $F:X\times Y\to ℝ\cup \{+\mathrm{\infty }\}$ が摂動函数であるための必要十分条件は、$F(x,0)=f(x)$ である。

双対性

テンプレート:仮リンクは、次の不等式の右辺と左辺の差で与えられる。

$\underset{y^{*}\in Y^{*}}{\sup }-F^{*}(0,y^{*})\le \underset{x\in X}{\inf }F(x,0),$

ここで $F^{*}$ は両変数についての凸共役である。

摂動函数 F をどのように選んでも弱双対性は成立する。また強双対性が成立するための条件は数多く存在する。例えば、F が真結合凸函数で、下半連続かつ $0\in \mathrm{core}({\mathrm{Pr}}_Y(\mathrm{dom}F))$ であり（ここで $\mathrm{core}$ は代数的内部を表し、${\mathrm{Pr}}_Y$ は ${\mathrm{Pr}}_Y(x,y)=y$ で定義される Y の上への射影である）、X と Y がフレシェ空間であるなら、強双対性は成立する。

例

ラグランジアン

$(X,X^{*})$ と $(Y,Y^{*})$ を双対組とする。（f(x) を最小化する）主問題と、関連する摂動函数 (F(x,y)) が与えられたとき、ラグランジアン $L:X\times Y^{*}\to ℝ\cup \{+\mathrm{\infty }\}$ は、F の y に関する負の共役（すなわち、凹共役）である。すなわち、ラグランジアンは次で定義される。

$L(x,-y^{*})=\underset{y\in Y}{\inf }\{F(x,y)-y^{*}(y)\}.$

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

$\underset{y^{*}\in Y^{*}}{\sup }-F^{*}(0,y^{*})=\underset{y^{*}\in Y^{*}}{\sup }\underset{x\in X}{\inf }L(x,y^{*})\le \underset{x\in X}{\inf }\underset{y^{*}\in Y^{*}}{\sup }L(x,y^{*})=\underset{x\in X}{\inf }F(x,0).$

主問題が、$\tilde{f}(x)=f(x)+I_{{ℝ}_{+}^d}(-g(x))$ に対し

$\underset{x:g(x)\le 0}{\inf }f(x)=\underset{x\in X}{\inf }\tilde{f}(x)$

で与えられるとする。このとき、摂動が

$\underset{x:g(x)\le y}{\inf }f(x)$

で与えられるなら、摂動函数は

$F(x,y)=f(x)+I_{{ℝ}_{+}^d}(y-g(x))$

となる。したがって、ラグランジアン双対性との関連は、L が明らかに次で与えられることから分かる。

$L(x,y^{*})=\{\begin{array}{cc}f(x)+y^{*}(g(x))& \text{if }{y}^{*}\in {ℝ}_{+}^d\\ -\mathrm{\infty }& \text{else}\end{array}$.

フェンシェル双対性

$(X,X^{*})$ と $(Y,Y^{*})$ を双対組とする。ある線型作用素 $T:X\to Y$ とその随伴作用素 $T^{*}:Y^{*}\to X^{*}$ の存在を仮定する。また主テンプレート:仮リンク（指示函数による制限も含む）は、$J:X\times Y\to ℝ\cup \{+\mathrm{\infty }\}$ に対して $f(x)=J(x,Tx)$ と表すことが出来るものとする。このとき、摂動函数は次で与えられる。

$F(x,y)=J(x,Tx-y)$.

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