摂動函数
数学の数理最適化の分野において、摂動函数(せつどうかんすう、英: perturbation function)とは、主問題と双対問題を関連づける任意の函数である。そのような任意の函数は元の問題の摂動を定義する事実から、その名が付けられた。多くの場合、この函数は制約条件をシフトする形状を取る[1]。
定義 編集
分離的な局所凸空間の二つの双対組 と が与えられるとする。このとき、与えられた函数 に対する主問題を次で定義する。
制約条件が存在するならば、それら制約条件を として函数 に含めてしまうこともできる。ここで は指示函数である。このとき が摂動函数であるための必要十分条件は、 である[1][3]。
双対性 編集
双対性のギャップは、次の不等式の右辺と左辺の差で与えられる。
摂動函数 F をどのように選んでも弱双対性は成立する。また強双対性が成立するための条件は数多く存在する[3]。例えば、F が真結合凸函数で、下半連続かつ であり(ここで は代数的内部を表し、 は で定義される Y の上への射影である)、X と Y がフレシェ空間であるなら、強双対性は成立する[1]。
例 編集
ラグランジアン 編集
と を双対組とする。(f(x) を最小化する)主問題と、関連する摂動函数 (F(x,y)) が与えられたとき、ラグランジアン は、F の y に関する負の共役(すなわち、凹共役)である。すなわち、ラグランジアンは次で定義される。
特に、弱双対ミニマックス方程式は次のように表される。
主問題が、 に対し
で与えられるとする。このとき、摂動が
で与えられるなら、摂動函数は
となる。したがって、ラグランジアン双対性との関連は、L が明らかに次で与えられることから分かる。
- .
フェンシェル双対性 編集
と を双対組とする。ある線型作用素 とその随伴作用素 の存在を仮定する。また主目的函数(指示函数による制限も含む)は、 に対して と表すことが出来るものとする。このとき、摂動函数は次で与えられる。
- .
特に、主目的函数が であるなら、摂動函数は で与えられるが、これはフェンシェル双対性の伝統的な定義である[5]。
脚注 編集
- ^ a b c Radu Ioan Boţ; Gert Wanka; Sorin-Mihai Grad (2009). Duality in Vector Optimization. Springer. ISBN 978-3-642-02885-4
- ^ J. P. Ponstein (2004). Approaches to the Theory of Optimization. Cambridge University Press. ISBN 978-0-521-60491-8
- ^ a b c Zălinescu, C. (2002). Convex analysis in general vector spaces. River Edge, NJ,: World Scientific Publishing Co., Inc. pp. 106–113. ISBN 981-238-067-1. MR1921556
- ^ Ernö Robert Csetnek (2010). 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. Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3
- ^ Radu Ioan Boţ (2010). Conjugate Duality in Convex Optimization. Springer. p. 68. ISBN 978-3-642-04899-9