摂動関数

数理最適化において、摂動関数とは、主問題および双対問題に関連する関数のことです。この名称は、そのような関数が初期問題に対する摂動を定義するという事実に由来します。多くの場合、これは制約条件をシフトさせる形をとります。^[1]

いくつかの文献では、値関数は摂動関数と呼ばれ、摂動関数は双関数と呼ばれています。^[2]

意味

二つの分離された局所凸空間の双対とが与えられます。関数が与えられれば、主問題は次のように定義できます。 $\left(X,X^{*}\right)$ $\left(Y,Y^{*}\right)$ $f:X\to \mathbb {R} \cup \{+\infty \}$

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

制約条件がある場合、関数にとすることで組み込むことができます。ここでは特性関数です。このときは摂動関数であり、のときのみ成立します。^[1]^[3] $f$ $f\leftarrow f+I_{\mathrm {constraints} }$ $I$ $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ $F(x,0)=f(x)$

二重性における使用

双対性ギャップとは、不等式の右辺と左辺の差である。

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),

ここで、両変数の凸共役である。 ^[3]^[4] $F^{*}$

摂動関数F の任意の選択に対して、弱双対性が成立する。いくつかの条件が満たされれば強双対性が成立する。^[3] 例えば、Fが真で、共凸で、（ここでは代数的内部、はによって定義されるYへの射影）と下半連続であり、 XとYがフレシェ空間である場合、強双対性が成立する。[ ^1] $0\in \operatorname {core} ({\Pr }_{Y}(\operatorname {dom} F))$ $\operatorname {core}$ ${\Pr }_{Y}$ ${\Pr }_{Y}(x,y)=y$

例

ラグランジアン

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

L(x,y^{*})=\inf _{y\in Y}\left\{F(x,y)-y^{*}(y)\right\}.

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

\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).

原初問題が次のように与えられるとすると

\inf _{x:g(x)\leq 0}f(x)=\inf _{x\in X}{\tilde {f}}(x)

ここで、摂動は ${\tilde {f}}(x)=f(x)+I_{\mathbb {R} _{+}^{d}}(-g(x))$

\inf _{x:g(x)\leq y}f(x)

摂動関数は

F(x,y)=f(x)+I_{\mathbb {R} _{+}^{d}}(y-g(x)).

このようにラグランジアン双対性への接続は、Lが次のように自明にわかることからわかる。

L(x,y^{*})={\begin{cases}f(x)-y^{*}(g(x))&{\text{if }}y^{*}\in \mathbb {R} _{-}^{d},\\-\infty &{\text{else}}.\end{cases}}

フェンチェルの二重性

とを双対とする。随伴作用素を持つ線型写像が存在するとする。主目的関数（指示関数による制約を含む）はとなるように書けるとする。このとき、摂動関数は次のように与えられる。 $(X,X^{*})$ $(Y,Y^{*})$ $T:X\to Y$ $T^{*}:Y^{*}\to X^{*}$ $f(x)$ $f(x)=J(x,Tx)$ $J:X\times Y\to \mathbb {R} \cup \{+\infty \}$

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

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

参考文献

^ abc ラドゥ・ヨアン・ボシュ;ガート・ワンカ。ソリン・ミハイ卒業生（2009 年）。ベクトル最適化の二重性。スプリンガー。ISBN 978-3-642-02885-4。
^ JP Ponstein (2004). 『最適化理論へのアプローチ』ケンブリッジ大学出版局. ISBN 978-0-521-60491-8。
^ abc Zălinescu, C. (2002).一般ベクトル空間における凸解析. リバーエッジ, ニュージャージー: World Scientific Publishing Co., Inc. pp. 106– 113. ISBN 981-238-067-1. MR 1921556。
^ Ernö Robert Csetnek (2010).凸最適化における古典的な一般化内点正則性条件の破綻の克服．双対性理論の最大単調作用素の拡大への応用．Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3。
^ Radu Ioan Boţ (2010).凸最適化における共役双対性. Springer. p. 68. ISBN 978-3-642-04899-9。

[BWG-1] ラドゥ・ヨアン・ボシュ;ガート・ワンカ。ソリン・ミハイ卒業生（2009 年）。ベクトル最適化の二重性。スプリンガー。ISBN 978-3-642-02885-4。

[2] JP Ponstein (2004). 『最適化理論へのアプローチ』ケンブリッジ大学出版局. ISBN 978-0-521-60491-8。

[Zalinescu-3] Zălinescu, C. (2002).一般ベクトル空間における凸解析. リバーエッジ, ニュージャージー: World Scientific Publishing Co., Inc. pp. 106– 113. ISBN 981-238-067-1. MR 1921556。

[4] Ernö Robert Csetnek (2010).凸最適化における古典的な一般化内点正則性条件の破綻の克服．双対性理論の最大単調作用素の拡大への応用．Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3。

[5] Radu Ioan Boţ (2010).凸最適化における共役双対性. Springer. p. 68. ISBN 978-3-642-04899-9。