自己 一致関数は、特定の 微分不等式 を満たす関数であり 、 ニュートン法 [1] を使用した 最適化が特に容易になります。 サブ6.2.4.2 自己 一致バリアは 、特定の自己一致関数であり、 特定の凸集合の バリア関数でもあります。自己一致バリアは、最適化のための 内点法 の重要な要素です。
自己一致関数
多変量自己一致関数 自己一致関数の一般的な定義は以下の通りである。 [2] : 定義2.0.1
C をR n の凸非空開集合と する 。 f を C 上で定義された 3 回連続微分可能な関数とする。 f が次の特性を満たす場合、
f は C 上で自己一致している という。
1. 障壁特性: C の境界点に収束する C 内の任意の点の列上で 、 f は ∞に収束します。
2. 微分不等式: C 内の すべての点 x と R n 内のすべての方向h に対して、 g h を 方向 h に制限された関数 f とします。つまり、 g h ( t ) = f ( x + t* h ) です。このとき、 1 次元関数 g h は 次の微分不等式を満たします。
|
グ
h
‴
（ x ）
|
≤ 2
グ
h
″
（ x
）
3
/
2
{\displaystyle |g_{h}'''(x)|\leq 2g_{h}'''(x)^{3/2}}
。
同様に: [3]
d
d α
∇
2
ふ （ x + α ええ ）
|
α = 0
⪯ 2
ええ
T
∇
2
ふ （ x ） ええ
∇
2
ふ （ x ）
{\displaystyle \left.{\frac {d}{d\alpha }}\nabla ^{2}f(x+\alpha y)\right|_{\alpha =0}\preceq 2{\sqrt {y^{T}\nabla ^{2}f(x)\,y}}\,\nabla ^{2}f(x)}
一変量自己一致関数 関数 が 自己一致するのは次の 場合です:
ふ :
R
→
R
{\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} }
R
{\displaystyle \mathbb {R} }
|
ふ ‴
（ x ）
|
≤ 2
ふ ″
（ x
）
3
/
2
{\displaystyle |f'''(x)|\leq 2f''(x)^{3/2}}
同様に、次の条件が満たされる場合 :
ふ ″
（ x ） > 0
{\displaystyle f''(x)>0}
|
d
d x
1
ふ ″
（ x ）
|
≤ 1
{\displaystyle \left|{\frac {d}{dx}}{\frac {1}{\sqrt {f''(x)}}}\right|\leq 1}
他の部分も満足します 。
ふ ‴
（ x ） = 0
{\displaystyle f'''(x)=0}
例 線形関数と凸二次関数は、3 次導関数がゼロであるため自己一致します。 が定義され、すべての に対して凸であり 、が成り立つ ことを検証する任意 の関数は 、 であるその定義域上で自己一致します 。いくつかの例を示します。
ふ （ x ） = − ログ （ − グ （ x ） ） − ログ x
{\displaystyle f(x)=-\log(-g(x))-\log x}
グ （ x ）
{\displaystyle g(x)}
x > 0
{\displaystyle x>0}
|
グ ‴
（ x ）
|
≤ 3
グ ″
（ x ）
/
x
{\displaystyle |g'''(x)|\leq 3g''(x)/x}
{ x ∣ x > 0 、 グ （ x ） < 0 }
{\displaystyle \{x\mid x>0,g(x)<0\}}
グ （ x ） = −
x
p
{\displaystyle g(x)=-x^{p}}
のために
0 < p ≤ 1
{\displaystyle 0<p\leq 1}
グ （ x ） = − ログ x
{\displaystyle g(x)=-\log x}
グ （ x ） =
x
p
{\displaystyle g(x)=x^{p}}
のために
− 1 ≤ p ≤ 0
{\displaystyle -1\leq p\leq 0}
グ （ x ） = （ 1つの x + b
）
2
/
x
{\displaystyle g(x)=(ax+b)^{2}/x}
条件を満たす任意 の関数に対して、 を持つ関数 も条件を満たします。
グ
{\displaystyle g}
グ （ x ） + 1つの
x
2
+ b x + c
{\displaystyle g(x)+ax^{2}+bx+c}
1つの ≥ 0
{\displaystyle a\geq 0}
自己一致しない関数:
ふ （ x ） =
e
x
{\displaystyle f(x)=e^{x}}
ふ （ x ） =
1
x
p
、 x > 0 、 p > 0
{\displaystyle f(x)={\frac {1}{x^{p}}},x>0,p>0}
ふ （ x ） =
|
x
p
|
、 p > 2
{\displaystyle f(x)=|x^{p}|,p>2}
自己一致障壁 自己一致障壁（SCB）の一般的な定義は以下のとおりである。 [2] : 定義3.1.1
C をR n 内の内部が空でない 凸閉集合と する。f を内部 ( C ) から R への関数とする 。M >0 を実パラメータとする。f が次の条件を満たす場合、 f は Cの M 自己一致障壁 である と言う 。
1. fは内部( C )上の自己一致関数である 。
2. interior( C )内の
あらゆる点 x と R n 内のあらゆる方向h に対して、 g h を 方向 h に制限された関数 f 、すなわち g h ( t ) = f ( x + t* h )とします。このとき、1次元関数 g h は 次の微分不等式を満たす必要があります。
|
グ
h
′
（ x ）
|
≤
ま
1
/
2
⋅
グ
h
″
（ x
）
1
/
2
{\displaystyle |g_{h}'(x)|\leq M^{1/2}\cdot g_{h}''(x)^{1/2}}
。
SCBの構築 内点法における SCB の重要性のため、さまざまなドメインに対して SCB を構築する方法を知ることが重要です。
理論的には、R nの すべての 閉凸領域にはパラメータ O( n )を持つ自己一致障壁が存在する ことが証明できる 。しかし、この「普遍障壁」は多変数積分によって与えられ、実際の計算には複雑すぎる。したがって、主な目標は効率的に計算可能な SCB を構築することである。 [4] : Sec.9.2.3.3
SCB はいくつかの基本的な SCB から構築することができ、いくつかの 組み合わせ規則 を使用して、より複雑なドメインの SCB を生成するために組み合わせることができます 。
基本的なSCB すべての定数は、パラメータM=0で、すべてのR n に対して自己一致障壁である。これは、空間全体に対して唯一の自己一致障壁であり、 M < 1で唯一の自己一致障壁である。 [2] ：例3.1.1 [線形関数と二次関数は自己一致関数であるが、自己一致障壁ではないことに注意 ] 。
正の半直線 ( ) の場合、 はパラメータ を持つ自己一致障壁です 。これは定義から直接証明できます。
R
+
{\displaystyle \mathbb {R} _{+}}
x > 0
{\displaystyle x>0}
ふ （ x ） = − 行 x
{\displaystyle f(x)=-\ln x}
ま = 1
{\displaystyle M=1}
置換ルール G を R n の閉凸領域とし 、 g を G の M -SCB とする 。 x = Ay + b を R k から R n へ の アフィン 写像とし、その像は G の内部と交差するものと する。 H を 写像 H = { y in R k | Ay+b in G } のもとでの G の逆像とする 。 h を 合成関数 h ( y ) := g( Ay + b ) とする。すると h は Hの M -SCB となる 。 [2] : Prop.3.1.1
たとえば、 n =1、 正 の半直線 G 、および を取ります。任意の k に対して、 a を k 要素のベクトル、 b をスカラーとします。H = { y in R k | a T y+b ≥ 0} = k 次元半空間とします 。 置換 規則 により 、 は H に対して 1 - SCB です 。 より 一般的な形式は H = { x in R k | a T x ≤ b} で、SCB は です 。
グ （ x ） = − 行 x
{\displaystyle g(x)=-\ln x}
h （ ええ ） = − 行 （
1つの
T
ええ + b ）
{\displaystyle h(y)=-\ln(a^{T}y+b)}
h （ ええ ） = − 行 （ b −
1つの
T
ええ ）
{\displaystyle h(y)=-\ln(b-a^{T}y)}
置換規則は、アフィン写像から特定のクラスの「適切な」写像 [2] : Thm.9.1.1 および二次写像[2] : Sub.9.3 に拡張することができる。
デカルト積の法則 1,..., mに属するすべての i について 、 G i を R ni に属する閉凸領域とし 、 g i を G i のM i -SCB とする 。 G を すべての G i の直積 とする 。 g(x 1 ,...,x m ) := sum i g i ( x i ) とする。すると、 g は G の SCB となり 、パラメータ sum i M i を持つ。 [2] : Prop.3.1.1
たとえば、すべての G i を 正の半直線とすると、 G は 正の直交座標になります 。を Gの m -SCB とします。
R
+
m
{\displaystyle \mathbb {R} _{+}^{m}}
g
(
x
)
=
−
∑
i
=
1
m
ln
x
i
{\displaystyle g(x)=-\sum _{i=1}^{m}\ln x_{i}}
ここで、置換規則を適用できます。1 ,..., m内の j について、線形不等式 a j T x ≤ b j によって定義される多面体について、スレーターの条件 を満たす場合 、 は m -SCB であることがわかります 。線形関数は、 2 次関数 に置き換えることができます 。
f
(
x
)
=
−
∑
i
=
1
m
ln
(
b
j
−
a
j
T
x
)
{\displaystyle f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)}
b
j
−
a
j
T
x
{\displaystyle b_{j}-a_{j}^{T}x}
交差ルール G 1 ,..., G m を R n の閉凸領域と する。1 ,..., m 内の各 i について、 g i を G i のM i -SCB とし 、 r i を 実数とする。G をすべての G i の共通部分とし 、その内部は空でないとする。g : = sum i r i *g i とする。すると、 g は G の SCB であり 、パラメータは sum i r i *M i である。 [2] : Prop.3.1.1
したがって、 G が 制約のリストによって定義されている場合は、制約ごとに SCB を個別に見つけ、それらを合計するだけで G の SCB を取得できます。
たとえば、ドメインが、 j が1,..., m の範囲内にある場合、 形式 a j T x ≤ b j のm 個の線形制約によって定義されているとします。この場合、交差規則を使用して m -SCB (以前に直積規則を使用して計算したものと同じもの)
を構築できます。
f
(
x
)
=
−
∑
i
=
1
m
ln
(
b
j
−
a
j
T
x
)
{\displaystyle f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)}
碑文のSCB 関数 f ( x ) のエピグラフ は 、関数のグラフの上の領域、つまり です。 f のエピグラフが 凸 集合となる のは、 fが 凸関数 である場合に限り ます。次の定理は、エピグラフが SCB を持つ関数 f を いくつか示しています。
{
(
x
,
t
)
∈
R
2
:
t
≥
f
(
x
)
}
{\displaystyle \{(x,t)\in \mathbb {R} ^{2}:t\geq f(x)\}}
g ( t ) を t >0 上の 3 回連続微分可能な凹関数とし、 すべての t >0 に対して定数 ( 3* b と表記) で制限されるものとする。G を 2 次元凸領域とする と、関数 f ( x , t ) = -ln(f(t)-x) - max[1,b 2 ]*ln(t) は G に対して自己一致障壁となり、パラメータは (1+max[1,b 2 ])となる 。 [2] : Prop.9.2.1
t
⋅
|
g
‴
(
t
)
|
/
|
g
″
(
t
)
|
{\displaystyle t\cdot |g'''(t)|/|g''(t)|}
G
=
closure
(
{
(
x
,
t
)
∈
R
2
:
t
>
0
,
x
≤
g
(
t
)
}
)
.
{\displaystyle G={\text{closure}}(\{(x,t)\in \mathbb {R} ^{2}:t>0,x\leq g(t)\}).}
例:
g ( t ) = t 1/ p （ある p ≥ 1）および b =(2 p -1)/(3 p )と します。すると、 には 2-SCB があります。同様に、 に は 2-SCB があります。交差規則を使用すると、 には 4-SCB があることがわかります。
G
1
=
{
(
x
,
t
)
∈
R
2
:
(
x
+
)
p
≤
t
}
{\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:(x_{+})^{p}\leq t\}}
G
2
=
{
(
x
,
t
)
∈
R
2
:
(
[
−
x
]
+
)
p
≤
t
}
{\displaystyle G_{2}=\{(x,t)\in \mathbb {R} ^{2}:([-x]_{+})^{p}\leq t\}}
G
=
G
1
∩
G
2
=
{
(
x
,
t
)
∈
R
2
:
|
x
|
p
≤
t
}
{\displaystyle G=G_{1}\cap G_{2}=\{(x,t)\in \mathbb {R} ^{2}:|x|^{p}\leq t\}}
g ( t )=ln( t )、 b =2/3と します。すると 2-SCBが存在します。
G
=
{
(
x
,
t
)
∈
R
2
:
e
x
≤
t
}
{\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:e^{x}\leq t\}}
これで、 p ノルムを最小化する問題の SCB を構築できます 。 、ここで v j は定数スカラー、 u j は定数ベクトル、 p >0 は定数です。まず、これを線形目的関数の最小化に変換します。 ただし、制約は [ m ] 内のすべての jに対して次のようになります。各制約に対して、アフィン置換規則により 4-SCB が得られます。交差規則を使用すると、実行可能領域全体の (4 n )-SCB が得られます 。
min
x
∑
j
=
1
n
|
v
j
−
x
T
u
j
|
p
{\displaystyle \min _{x}\sum _{j=1}^{n}|v_{j}-x^{T}u_{j}|^{p}}
min
x
∑
j
=
1
n
t
j
{\displaystyle \min _{x}\sum _{j=1}^{n}t_{j}}
t
j
≥
|
v
j
−
x
T
u
j
|
p
{\displaystyle t_{j}\geq |v_{j}-x^{T}u_{j}|^{p}}
同様に、 g を x >0上の 3 回連続微分可能な凸関数とし、 すべての x >0に対して 次が成り立つものとする。G を 2 次元凸領域とする: closure({ ( t,x ) in R 2 : x>0, t ≥ g ( x ) })。すると、関数 f ( x , t ) = -ln(tf(x)) - max[1,b 2 ]*ln(x) は G の自己一致障壁となり、パラメータは (1+max[1,b 2 ]) となる。 [2] : Prop.9.2.2
x
⋅
|
g
‴
(
x
)
|
/
|
g
″
(
x
)
|
≤
3
b
{\displaystyle x\cdot |g'''(x)|/|g''(x)|\leq 3b}
例:
g ( x ) = x - p （ある p >0 に対して）とし 、b=(2+ p )/3 とします。すると 2-SCB が存在します。
G
1
=
{
(
x
,
t
)
∈
R
2
:
x
−
p
≤
t
,
x
≥
0
}
{\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:x^{-p}\leq t,x\geq 0\}}
g ( x )= x ln( x )、 b =1/3と します。すると 2-SCBが存在します。
G
=
{
(
x
,
t
)
∈
R
2
:
x
ln
x
≤
t
,
x
≥
0
}
{\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:x\ln x\leq t,x\geq 0\}}
コーン用SCB 2 次円錐 の場合 、関数は 自己一致バリアです。
{
(
x
,
y
)
∈
R
n
−
1
×
R
∣
‖
x
‖
≤
y
}
{\displaystyle \{(x,y)\in \mathbb {R} ^{n-1}\times \mathbb {R} \mid \|x\|\leq y\}}
f
(
x
,
y
)
=
−
log
(
y
2
−
x
T
x
)
{\displaystyle f(x,y)=-\log(y^{2}-x^{T}x)}
m*m 対称行列の半正定値 円錐の場合 、関数は 自己一致障壁です。
f
(
A
)
=
−
log
det
A
{\displaystyle f(A)=-\log \det A}
が 半正定値 対称行列で ある 二次領域で定義されるとき 、対数障壁は 次式と自己一致する。
ϕ
(
x
)
>
0
{\displaystyle \phi (x)>0}
ϕ
(
x
)
=
α
+
⟨
a
,
x
⟩
−
1
2
⟨
A
x
,
x
⟩
{\displaystyle \phi (x)=\alpha +\langle a,x\rangle -{\frac {1}{2}}\langle Ax,x\rangle }
A
=
A
T
≥
0
{\displaystyle A=A^{T}\geq 0}
f
(
x
)
=
−
log
ϕ
(
x
)
{\displaystyle f(x)=-\log \phi (x)}
M
=
2
{\displaystyle M=2}
指数錐の場合 、関数は 自己一致障壁です。
{
(
x
,
y
,
z
)
∈
R
3
∣
y
e
x
/
y
≤
z
,
y
>
0
}
{\displaystyle \{(x,y,z)\in \mathbb {R} ^{3}\mid ye^{x/y}\leq z,y>0\}}
f
(
x
,
y
,
z
)
=
−
log
(
y
log
(
z
/
y
)
−
x
)
−
log
z
−
log
y
{\displaystyle f(x,y,z)=-\log(y\log(z/y)-x)-\log z-\log y}
パワーコーン の場合 、関数は 自己一致バリアです。
{
(
x
1
,
x
2
,
y
)
∈
R
+
2
×
R
∣
|
y
|
≤
x
1
α
x
2
1
−
α
}
{\displaystyle \{(x_{1},x_{2},y)\in \mathbb {R} _{+}^{2}\times \mathbb {R} \mid |y|\leq x_{1}^{\alpha }x_{2}^{1-\alpha }\}}
f
(
x
1
,
x
2
,
y
)
=
−
log
(
x
1
2
α
x
2
2
(
1
−
α
)
−
y
2
)
−
log
x
1
−
log
x
2
{\displaystyle f(x_{1},x_{2},y)=-\log(x_{1}^{2\alpha }x_{2}^{2(1-\alpha )}-y^{2})-\log x_{1}-\log x_{2}}
歴史 1994年の著書 [6 ]の「参考文献コメント」 [5] で述べられているように、自己一致関数は1988年に ユーリ・ネステロフ [7] [8] によって導入され、 アルカディ・ネミロフスキー [9] によってさらに発展しました。 [10] で説明されているように 、彼らの基本的な観察は、ニュートン法がアフィン不変であるということでした。つまり、関数に対して ニュートンステップがある場合、 が非退化線形変換で ある 関数に対して、から始めて 、再帰的に示すことができる
ニュートンステップがあるということです。
f
(
x
)
{\displaystyle f(x)}
x
k
+
1
=
x
k
−
[
f
″
(
x
k
)
]
−
1
f
′
(
x
k
)
{\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})}
ϕ
(
y
)
=
f
(
A
y
)
{\displaystyle \phi (y)=f(Ay)}
A
{\displaystyle A}
y
0
=
A
−
1
x
0
{\displaystyle y_{0}=A^{-1}x_{0}}
y
k
=
A
−
1
x
k
{\displaystyle y_{k}=A^{-1}x_{k}}
y
k
+
1
=
y
k
−
[
ϕ
″
(
y
k
)
]
−
1
ϕ
′
(
y
k
)
=
y
k
−
[
A
T
f
″
(
A
y
k
)
A
]
−
1
A
T
f
′
(
A
y
k
)
=
A
−
1
x
k
−
A
−
1
[
f
″
(
x
k
)
]
−
1
f
′
(
x
k
)
=
A
−
1
x
k
+
1
{\displaystyle y_{k+1}=y_{k}-[\phi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1}A^{T}f'(Ay_{k})=A^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f'(x_{k})=A^{-1}x_{k+1}}
。 しかし、ニュートン法の標準的な解析では、 のヘッセ行列はリプシッツ連続、つまりある定数 に対して であると仮定しています 。 が 3 回 連続 微分可能であると仮定すると、これは次と同等です。
f
{\displaystyle f}
‖
f
″
(
x
)
−
f
″
(
y
)
‖
≤
M
‖
x
−
y
‖
{\displaystyle \|f''(x)-f''(y)\|\leq M\|x-y\|}
M
{\displaystyle M}
f
{\displaystyle f}
|
⟨
f
‴
(
x
)
[
u
]
v
,
v
⟩
|
≤
M
‖
u
‖
‖
v
‖
2
{\displaystyle |\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}}
全ての
u
,
v
∈
R
n
{\displaystyle u,v\in \mathbb {R} ^{n}}
ここで、 です 。すると、上記の不等式の左辺はアフィン変換に対して不変です が、右辺はそうではありません。
f
‴
(
x
)
[
u
]
=
lim
α
→
0
α
−
1
[
f
″
(
x
+
α
u
)
−
f
″
(
x
)
]
{\displaystyle f'''(x)[u]=\lim _{\alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]}
f
(
x
)
→
ϕ
(
y
)
=
f
(
A
y
)
,
u
→
A
−
1
u
,
v
→
A
−
1
v
{\displaystyle f(x)\to \phi (y)=f(Ay),u\to A^{-1}u,v\to A^{-1}v}
著者らは、ユークリッド計量を のヘッセ行列によって定義されるスカラー積に置き換えることで、右辺も不変にできることを指摘している 。すると、自己一致関数の定義が次のように得
られる 。
f
{\displaystyle f}
‖
w
‖
f
″
(
x
)
=
⟨
f
″
(
x
)
w
,
w
⟩
1
/
2
{\displaystyle \|w\|_{f''(x)}=\langle f''(x)w,w\rangle ^{1/2}}
w
∈
R
n
{\displaystyle w\in \mathbb {R} ^{n}}
|
⟨
f
‴
(
x
)
[
u
]
u
,
u
⟩
|
≤
M
⟨
f
″
(
x
)
u
,
u
⟩
3
/
2
{\displaystyle |\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}}
。
プロパティ
線形結合 およびが定数 および および と 自己一致している 場合 、 は 定数 と自己一致します 。
f
1
{\displaystyle f_{1}}
f
2
{\displaystyle f_{2}}
M
1
{\displaystyle M_{1}}
M
2
{\displaystyle M_{2}}
α
,
β
>
0
{\displaystyle \alpha ,\beta >0}
α
f
1
+
β
f
2
{\displaystyle \alpha f_{1}+\beta f_{2}}
max
(
α
−
1
/
2
M
1
,
β
−
1
/
2
M
2
)
{\displaystyle \max(\alpha ^{-1/2}M_{1},\beta ^{-1/2}M_{2})}
が定数 と自己一致し 、 が のアフィン変換である 場合 、 は パラメータ とも自己一致します 。
f
{\displaystyle f}
M
{\displaystyle M}
A
x
+
b
{\displaystyle Ax+b}
R
n
{\displaystyle \mathbb {R} ^{n}}
ϕ
(
x
)
=
f
(
A
x
+
b
)
{\displaystyle \phi (x)=f(Ax+b)}
M
{\displaystyle M}
凸共役 が自己一致する ならば、その 凸共役 も自己一致する。 [6] [11]
f
{\displaystyle f}
f
∗
{\displaystyle f^{*}}
非特異ヘッセ行列 が自己一致し、 の定義域に 直線（両方向に無限）が含まれない 場合、 は 非特異です。
f
{\displaystyle f}
f
{\displaystyle f}
f
″
{\displaystyle f''}
逆に、 の領域にあるいくつ かに対して が成り立つ場合 、が の領域に ある すべての に対してが成り立ち 、 は 線形であり最大値を持つことはできないため、 はすべて の 領域にあります。 は、 その領域内に最小値を持つことはできない
ことにも注意してください。
x
{\displaystyle x}
f
{\displaystyle f}
u
∈
R
n
,
u
≠
0
{\displaystyle u\in \mathbb {R} ^{n},u\neq 0}
⟨
f
″
(
x
)
u
,
u
⟩
=
0
{\displaystyle \langle f''(x)u,u\rangle =0}
⟨
f
″
(
x
+
α
u
)
u
,
u
⟩
=
0
{\displaystyle \langle f''(x+\alpha u)u,u\rangle =0}
α
{\displaystyle \alpha }
x
+
α
u
{\displaystyle x+\alpha u}
f
{\displaystyle f}
f
(
x
+
α
u
)
{\displaystyle f(x+\alpha u)}
x
+
α
u
,
α
∈
R
{\displaystyle x+\alpha u,\alpha \in \mathbb {R} }
f
{\displaystyle f}
f
{\displaystyle f}
アプリケーション とりわけ、自己一致関数は ニュートン法 の解析に役立ちます。自己一致 バリア関数は、凸および非線形最適化の 内点法 で使用される バリア関数を 開発するために使用されます 。ニュートン法の通常の解析はバリア関数には機能しません。バリア関数の 2 次導関数はリプシッツ連続にはならず、そうでなければバリア関数は の任意のコンパクトな部分集合で制限されるからです 。
R
n
{\displaystyle \mathbb {R} ^{n}}
自己一致バリア機能
制約付き最適化手法において障壁として使用できる関数のクラスである。 通常の場合と同様に、証明可能な収束特性を持つニュートンアルゴリズムを使用して最小化することができます（ただし、これらの結果を導くのはやや困難です） 上記の両方を満たすには、関数の3次導関数の通常の定数境界（ニュートン法の通常の収束結果を得るために必要）をヘッセ行列に対する境界に置き換える。
自己一致関数の最小化 自己一致関数は、収束に必要なステップ数に制限がある修正ニュートン法で最小化できます。ここでは、 が 標準 的な 自己一致関数、つまりパラメータ と自己一致していると仮定します 。
f
{\displaystyle f}
M
=
2
{\displaystyle M=2}
における ニュートン減衰を 、 における ヘッセ行列によって定義される局所ノルムにおける ニュートンステップの大きさとして 定義する。
λ
f
(
x
)
{\displaystyle \lambda _{f}(x)}
f
{\displaystyle f}
x
{\displaystyle x}
[
f
″
(
x
)
]
−
1
f
′
(
x
)
{\displaystyle [f''(x)]^{-1}f'(x)}
f
{\displaystyle f}
x
{\displaystyle x}
λ
f
(
x
)
=
⟨
f
″
(
x
)
[
f
″
(
x
)
]
−
1
f
′
(
x
)
,
[
f
″
(
x
)
]
−
1
f
′
(
x
)
⟩
1
/
2
=
⟨
[
f
″
(
x
)
]
−
1
f
′
(
x
)
,
f
′
(
x
)
⟩
1
/
2
{\displaystyle \lambda _{f}(x)=\langle f''(x)[f''(x)]^{-1}f'(x),[f''(x)]^{-1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1}f'(x),f'(x)\rangle ^{1/2}}
すると、 の領域においてに対して 、 であれば 、ニュートン反復法が証明可能であることが分かる。
x
{\displaystyle x}
f
{\displaystyle f}
λ
f
(
x
)
<
1
{\displaystyle \lambda _{f}(x)<1}
x
+
=
x
−
[
f
″
(
x
)
]
−
1
f
′
(
x
)
{\displaystyle x_{+}=x-[f''(x)]^{-1}f'(x)}
も の領域内になります 。これは の自己一致に基づいて 、 の値に有限の境界を与えることができるためです 。さらに、
f
{\displaystyle f}
f
{\displaystyle f}
f
(
x
+
)
{\displaystyle f(x_{+})}
λ
f
(
x
+
)
≤
(
λ
f
(
x
)
1
−
λ
f
(
x
)
)
2
{\displaystyle \lambda _{f}(x_{+})\leq {\Bigg (}{\frac {\lambda _{f}(x)}{1-\lambda _{f}(x)}}{\Bigg )}^{2}}
そして、もし私たちが
λ
f
(
x
)
<
λ
¯
=
3
−
5
2
{\displaystyle \lambda _{f}(x)<{\bar {\lambda }}={\frac {3-{\sqrt {5}}}{2}}}
となることも保証されている ので、収束するまでニュートン法を使い続けることができます。 に対して、 が 0 に 2 次収束するのは となることに注意してください 。 これ により 、 が に 、 が に 2次収束することが示されます。ただし、 は 次の定理により得られます。 の
場合、
λ
f
(
x
+
)
<
λ
f
(
x
)
{\displaystyle \lambda _{f}(x_{+})<\lambda _{f}(x)}
λ
f
(
x
+
)
<
β
{\displaystyle \lambda _{f}(x_{+})<\beta }
β
∈
(
0
,
λ
¯
)
{\displaystyle \beta \in (0,{\bar {\lambda }})}
λ
f
{\displaystyle \lambda _{f}}
λ
f
(
x
+
)
≤
(
1
−
β
)
−
2
λ
f
(
x
)
2
{\displaystyle \lambda _{f}(x_{+})\leq (1-\beta )^{-2}\lambda _{f}(x)^{2}}
f
(
x
k
)
{\displaystyle f(x_{k})}
f
(
x
∗
)
{\displaystyle f(x^{*})}
x
{\displaystyle x}
x
∗
{\displaystyle x^{*}}
x
∗
=
arg
min
f
(
x
)
{\displaystyle x^{*}=\arg \min f(x)}
λ
f
(
x
)
<
1
{\displaystyle \lambda _{f}(x)<1}
ω
(
λ
f
(
x
)
)
≤
f
(
x
)
−
f
(
x
∗
)
≤
ω
∗
(
λ
f
(
x
)
)
{\displaystyle \omega (\lambda _{f}(x))\leq f(x)-f(x^{*})\leq \omega _{*}(\lambda _{f}(x))}
ω
′
(
λ
f
(
x
)
)
≤
‖
x
−
x
∗
‖
x
≤
ω
∗
′
(
λ
f
(
x
)
)
{\displaystyle \omega '(\lambda _{f}(x))\leq \|x-x^{*}\|_{x}\leq \omega _{*}'(\lambda _{f}(x))}
以下の定義に従う
ω
(
t
)
=
t
−
log
(
1
+
t
)
{\displaystyle \omega (t)=t-\log(1+t)}
ω
∗
(
t
)
=
−
t
−
log
(
1
−
t
)
{\displaystyle \omega _{*}(t)=-t-\log(1-t)}
‖
u
‖
x
=
⟨
f
″
(
x
)
u
,
u
⟩
1
/
2
{\displaystyle \|u\|_{x}=\langle f''(x)u,u\rangle ^{1/2}}
ニュートン法をある値から始める場合 、次 のように定義される
減衰ニュートン法 から始める必要があります。
x
0
{\displaystyle x_{0}}
λ
f
(
x
0
)
≥
λ
¯
{\displaystyle \lambda _{f}(x_{0})\geq {\bar {\lambda }}}
x
k
+
1
=
x
k
−
1
1
+
λ
f
(
x
k
)
[
f
″
(
x
k
)
]
−
1
f
′
(
x
k
)
{\displaystyle x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})}
このため、 は前に定義したとおりで あることが示されます 。は の 増加関数であるため 、 任意の に対してとなることに注意してください。 したがって、 の値は 各反復で一定量ずつ減少することが保証され、これは が のドメイン内にあることも証明します 。
f
(
x
k
+
1
)
≤
f
(
x
k
)
−
ω
(
λ
f
(
x
k
)
)
{\displaystyle f(x_{k+1})\leq f(x_{k})-\omega (\lambda _{f}(x_{k}))}
ω
{\displaystyle \omega }
ω
(
t
)
{\displaystyle \omega (t)}
t
>
0
{\displaystyle t>0}
ω
(
t
)
≥
ω
(
λ
¯
)
{\displaystyle \omega (t)\geq \omega ({\bar {\lambda }})}
t
≥
λ
¯
{\displaystyle t\geq {\bar {\lambda }}}
f
{\displaystyle f}
x
k
+
1
{\displaystyle x_{k+1}}
f
{\displaystyle f}
参考文献
^ Nemirovsky と Ben-Tal (2023). 「最適化 III: 凸最適化」 (PDF) 。 ^ abcdefghij Arkadi Nemirovsky (2004). 「凸計画法における内点多項式時間法」. ^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). 凸最適化 (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3 . 2011年 10月15日 閲覧 。 ^ Nemirovsky と Ben-Tal (2023). 「最適化 III: 凸最適化」 (PDF) 。 ^ Nesterov, Yurii; Nemirovskii, Arkadii ( 1994 年 1 月)。凸計画法における内点多項式アルゴリズム (参考文献コメント)。工業応用数学協会。doi : 10.1137 /1.9781611970791.bm。ISBN 978-0-89871-319-0 。 ^ ab Nesterov, Yurii; Nemirovskii, Arkadii (1994). 凸計画法における内点多項式アルゴリズム . 応用数学と数値数学の研究. 第 13 巻. doi :10.1137/1.9781611970791. ISBN 978-0-89871-319-0 . OCLC 29310677. [ ページが必要 ] ^ ゆ。 E. NESTEROV、線形および二次計画法の多項式時間法、Izvestija AN SSSR、Tekhnitcheskaya kibernetika、No. 3、1988、324-326 ページ。 (ロシア語で。) ^ Yu. E. NESTEROV、「線形および二次計画法における多項式時間反復法」、Voprosy kibernetiki、モスクワ、1988 年、pp. 102-125。(ロシア語) ^ YE Nesterov および AS Nemirovski、「凸計画法における自己一致関数と多項式時間法」、技術レポート、ソ連科学アカデミー中央経済数学研究所、モスクワ、ソ連、1989 年。 ^ Nesterov, I︠U︡. E. (2013年12月). 凸最適化入門講義：基礎コース. ボストン. ISBN 978-1-4419-8853-9 . OCLC 883391994. {{cite book}}: CS1 maint: location missing publisher (link)^ Sun, Tianxiao; Tran-Dinh, Quoc (2018). 「一般化された自己一致関数: ニュートン型法のレシピ」. 数学プログラミング : 命題6. arXiv : 1703.04599 .
![{\displaystyle G_{2}=\{(x,t)\in \mathbb {R} ^{2}:([-x]_{+})^{p}\leq t\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e99958b9b0f09e9639e83e5389792850771ab8d6)
![{\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b245be5eaf43c895ecbf35ac63b40f8bec01c5dd)
![{\displaystyle y_{k+1}=y_{k}-[\phi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1}A^{T}f'(Ay_{k})=A ^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f'(x_{k})=A^{-1}x_{k +1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2df3f5c8b059191e6dcf59392a108ceea7d34e9c)
![{\displaystyle |\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74a78be152f1db6516a4fc96859cec5b955325b9)
![{\displaystyle f'''(x)[u]=\lim _{\alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1be966179e3181d99a56918315085324cdfb0808)
![{\displaystyle |\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2cd02fb992e681dfb6d072b3ed75665265a8e48a)
![{\displaystyle [f''(x)]^{-1}f'(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2cba2421b936cb79d5ab8c68d8aca828ae028a3)
![{\displaystyle \lambda _{f}(x)=\langle f''(x)[f''(x)]^{-1}f'(x),[f''(x)]^{ -1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1}f'(x),f'(x)\rangle ^{1/2 }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebdbe02bad547b15d7693147b0318bc981a97e8d)
![{\displaystyle x_{+}=x-[f''(x)]^{-1}f'(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/322071437533f8751f1457a642861d1afd834280)
![{\displaystyle x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca8d4a1ca3d9fac68d5fb62ba65cff0b40a11a54)
