摂動函数のソースを表示

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

文献によっては、{{仮リンク|間接効用函数|label=価値函数|en|Indirect utility function}}が摂動函数と呼ばれ、摂動函数は二重函数（bifunction）と呼ばれることもある<ref>{{cite book|title=Approaches to the Theory of Optimization|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\colon X \to \mathbb{R} \cup \{+\infty\}</math> に対する主問題を次で定義する。

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

制約条件が存在するならば、それら制約条件を <math>f = f + I_\text{constraints}</math> として函数 <math>f</math> に含めてしまうこともできる。ここで <math>I</math> は{{仮リンク|特性函数 (凸解析)|label=指示函数|en|Characteristic function (convex analysis)}}である。このとき <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>。

== 双対性 ==
{{仮リンク|双対性のギャップ|en|duality gap}}は、次の不等式の右辺と左辺の差で与えられる。

:<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}(\operatorname{Pr}_Y(\operatorname{dom}F))</math> であり（ここで <math>\operatorname{core}</math> は[[代数的内部]]を表し、<math>\operatorname{Pr}_Y</math> は <math>\operatorname{Pr}_Y(x,y) = y</math> で定義される ''Y'' の上への[[射影 (集合論)|射影]]である）、''X'' と ''Y'' が[[フレシェ空間]]であるなら、強双対性は成立する<ref name="BWG" />。

== 例 ==

=== ラグランジアン ===
<math>(X,X^*)</math> と <math>(Y,Y^*)</math> を双対組とする。（''f(x)'' を最小化する）主問題と、関連する摂動函数 (''F(x,y)'') が与えられたとき、'''[[ラグランジアン]]''' <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>

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

:<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>\tilde{f}(x) = f(x) + I_{\mathbb{R}^d_+}(-g(x))</math> に対し

:<math>\inf_{x: g(x) \leq 0} f(x) = \inf_{x \in X} \tilde{f}(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> の存在を仮定する。また主{{仮リンク|損失函数|label=目的函数|en|Loss function}}（指示函数による制限も含む）は、<math>J: X \times Y \to \mathbb{R} \cup \{+\infty\}</math> に対して <math>f(x) = J(x,Tx)</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:線型計画法]]
[[Category:凸最適化]]
[[Category:数学に関する記事]]