数学 の数理最適化 の分野において、摂動函数 （せつどうかんすう、英 : perturbation function ）とは、主問題と双対問題 を関連づける任意の函数 である。そのような任意の函数は元の問題の摂動を定義する事実から、その名が付けられた。多くの場合、この函数は制約条件をシフトする形状を取る[ 1]
文献によっては、価値函数 （英語版 ） [ 2]
分離的 な局所凸空間 の二つの双対組
(
X
,
X
∗
)
{\displaystyle \left(X,X^{*}\right)}
(
Y
,
Y
∗
)
{\displaystyle \left(Y,Y^{*}\right)}
f
:
X
→
R
∪
{
+
∞
}
{\displaystyle f\colon X\to \mathbb {R} \cup \{+\infty \}}
inf
x
∈
X
f
(
x
)
.
{\displaystyle \inf _{x\in X}f(x).\,}
制約条件が存在するならば、それら制約条件を
f
=
f
+
I
constraints
{\displaystyle f=f+I_{\text{constraints}}}
f
{\displaystyle f}
I
{\displaystyle I}
指示函数 （英語版 ）
F
:
X
×
Y
→
R
∪
{
+
∞
}
{\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}
F
(
x
,
0
)
=
f
(
x
)
{\displaystyle F(x,0)=f(x)}
[ 1] [ 3]
双対性のギャップ （英語版 ）
sup
y
∗
∈
Y
∗
−
F
∗
(
0
,
y
∗
)
≤
inf
x
∈
X
F
(
x
,
0
)
,
{\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),}
ここで
F
∗
{\displaystyle F^{*}}
凸共役 である[ 3] [ 4]
摂動函数 F をどのように選んでも弱双対性 は成立する。また強双対性 が成立するための条件は数多く存在する[ 3] F が真 結合凸函数 で、下半連続 かつ
0
∈
core
(
Pr
Y
(
dom
F
)
)
{\displaystyle 0\in \operatorname {core} (\operatorname {Pr} _{Y}(\operatorname {dom} F))}
core
{\displaystyle \operatorname {core} }
代数的内部 を表し、
Pr
Y
{\displaystyle \operatorname {Pr} _{Y}}
Pr
Y
(
x
,
y
)
=
y
{\displaystyle \operatorname {Pr} _{Y}(x,y)=y}
Y の上への射影 である）、X と Y がフレシェ空間 であるなら、強双対性は成立する[ 1]
(
X
,
X
∗
)
{\displaystyle (X,X^{*})}
(
Y
,
Y
∗
)
{\displaystyle (Y,Y^{*})}
f(x) を最小化する）主問題と、関連する摂動函数 (F(x,y) ) が与えられたとき、ラグランジアン
L
:
X
×
Y
∗
→
R
∪
{
+
∞
}
{\displaystyle L:X\times Y^{*}\to \mathbb {R} \cup \{+\infty \}}
F の y に関する負の共役（すなわち、凹共役）である。すなわち、ラグランジアンは次で定義される。
L
(
x
,
−
y
∗
)
=
inf
y
∈
Y
{
F
(
x
,
y
)
−
y
∗
(
y
)
}
.
{\displaystyle L(x,-y^{*})=\inf _{y\in Y}\left\{F(x,y)-y^{*}(y)\right\}.}
特に、弱双対 ミニマックス方程式は次のように表される。
sup
y
∗
∈
Y
∗
−
F
∗
(
0
,
y
∗
)
=
sup
y
∗
∈
Y
∗
inf
x
∈
X
L
(
x
,
y
∗
)
≤
inf
x
∈
X
sup
y
∗
∈
Y
∗
L
(
x
,
y
∗
)
=
inf
x
∈
X
F
(
x
,
0
)
.
{\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).}
主問題が、
f
~
(
x
)
=
f
(
x
)
+
I
R
+
d
(
−
g
(
x
)
)
{\displaystyle {\tilde {f}}(x)=f(x)+I_{\mathbb {R} _{+}^{d}}(-g(x))}
inf
x
:
g
(
x
)
≤
0
f
(
x
)
=
inf
x
∈
X
f
~
(
x
)
{\displaystyle \inf _{x:g(x)\leq 0}f(x)=\inf _{x\in X}{\tilde {f}}(x)}
で与えられるとする。このとき、摂動が
inf
x
:
g
(
x
)
≤
y
f
(
x
)
{\displaystyle \inf _{x:g(x)\leq y}f(x)}
で与えられるなら、摂動函数は
F
(
x
,
y
)
=
f
(
x
)
+
I
R
+
d
(
y
−
g
(
x
)
)
{\displaystyle F(x,y)=f(x)+I_{\mathbb {R} _{+}^{d}}(y-g(x))}
となる。したがって、ラグランジアン双対性との関連は、L が明らかに次で与えられることから分かる。
L
(
x
,
y
∗
)
=
{
f
(
x
)
+
y
∗
(
g
(
x
)
)
if
y
∗
∈
R
+
d
−
∞
else
{\displaystyle L(x,y^{*})={\begin{cases}f(x)+y^{*}(g(x))&{\text{if }}y^{*}\in \mathbb {R} _{+}^{d}\\-\infty &{\text{else}}\end{cases}}}
(
X
,
X
∗
)
{\displaystyle (X,X^{*})}
(
Y
,
Y
∗
)
{\displaystyle (Y,Y^{*})}
線型作用素
T
:
X
→
Y
{\displaystyle T:X\to Y}
随伴作用素
T
∗
:
Y
∗
→
X
∗
{\displaystyle T^{*}:Y^{*}\to X^{*}}
目的函数 （英語版 ）
J
:
X
×
Y
→
R
∪
{
+
∞
}
{\displaystyle J:X\times Y\to \mathbb {R} \cup \{+\infty \}}
f
(
x
)
=
J
(
x
,
T
x
)
{\displaystyle f(x)=J(x,Tx)}
F
(
x
,
y
)
=
J
(
x
,
T
x
−
y
)
{\displaystyle F(x,y)=J(x,Tx-y)}
特に、主目的函数が
f
(
x
)
+
g
(
T
x
)
{\displaystyle f(x)+g(Tx)}
F
(
x
,
y
)
=
f
(
x
)
+
g
(
T
x
−
y
)
{\displaystyle F(x,y)=f(x)+g(Tx-y)}
[ 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 . MR 1921556
^ 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
