ウルフ条件

ウルフ条件（ウルフじょうけん、テンプレート:Lang-en-short）とは、無制約最適化問題において非厳密直線探索を行う際に用いられる一連の不等式をいう。特に準ニュートン法を行う際によく用いられる。1969年にテンプレート:仮リンクが初めて発表した。

ある滑らかな関数 $f:{ℝ}^n\to ℝ$ について無制約最適化問題 $$\underset{x}{\min }f(𝒙)$$ を解く際、近似的な部分問題 $$\underset{\alpha }{\min }f({𝒙}_k+\alpha {𝒑}_k)$$ を解くことがしばしばある。ここで テンプレート:Mvar は現在の反復における最適推定解、${𝒑}_k\in {ℝ}^n$ は探索方向、$\alpha \in ℝ$ はステップ長である。

非厳密直線探索は、損失関数を厳密に最小化するのではなく、「十分に」小さくするステップ長 $\alpha \in {ℝ}^{+}$ を得る効率的な方法を提供する。これを行う際、ウルフ条件は新たな探索方向 テンプレート:Mvar を探索する前にある テンプレート:Mvar の推定値が満たすべき条件として用いられる。

アルミホ条件と曲率条件

あるステップ長 テンプレート:Mvar がウルフ条件を満たすとは、探索方向 テンプレート:Mvar が与えられたものとして以下の2つの不等式が成り立つことをいう。テンプレート:Ordered list ここで、テンプレート:Math である（不等式iiを評価する際、たとえば最急降下法の場合は ${𝒑}_k=-\mathrm{\nabla }f({𝒙}_k)$、ニュートン法の場合は ${𝒑}_k=-{𝑯}^{-1}\mathrm{\nabla }f({𝒙}_k)$ で テンプレート:Mvar が正定値行列であるため ${𝒑}_k^{\mathrm{\top }}\mathrm{\nabla }f({𝒙}_k)<0$ が成り立つことに留意する）。

テンプレート:Math は十分に小さく、テンプレート:Math は十分に大きくとることが多い。テンプレート:仮リンクとライトはニュートン法および準ニュートン法については テンプレート:Math、非線形共役勾配法については テンプレート:Math を例として与えている。不等式iはアルミホ条件テンプレート:Efnと呼ばれ、不等式iiは曲率条件と呼ばれる。不等式iはステップ長 テンプレート:Mvar が テンプレート:Mvar を「十分に」減少させることを、iiは勾配が十分に減少したことを保証する。条件iおよびiiはステップ長の上限と下限をそれぞれ与えるものとして解釈することができる。

強いウルフ条件

方向 テンプレート:Mvar に制限した一変数関数 テンプレート:Math を考える。ウルフ条件は テンプレート:Mvar の最適点からは遠いステップ長を与える場合がある。曲率条件を次のように変更したとする: テンプレート:Ordered list。iおよびiiiは強いウルフ条件と呼ばれ、テンプレート:Mvar を テンプレート:Mvar の臨界点付近に制限する。

理論的根拠

最適化アルゴリズムにウルフ条件を課す主な理由は、勾配がゼロに収束することを保証するためである。特に、テンプレート:Mvar と勾配とのテンプレート:仮リンク $$\cos {\theta }_k=\frac{\mathrm{\nabla }f({𝐱}_k{)}^{\mathrm{T}}{𝐩}_k}{\Vert \mathrm{\nabla }f({𝐱}_k)\Vert \Vert {𝐩}_k\Vert }$$ がゼロから遠くかつ条件iおよびiiが満たされる場合、$\mathrm{\nabla }f({𝐱}_k)\to 0$ が成り立つ。

もうひとつの動機は、${𝒑}_k=-B_k^{-1}\mathrm{\nabla }f({𝒙}_k)$ のように方向を求める準ニュートン法の場合、行列 テンプレート:Mvar をBFGS法やDFP法で更新する。テンプレート:Mvar が正定値かつiおよびiiが成り立つならば テンプレート:Math も正定値となる。

注意

ウルフ条件はアルミホ条件よりも複雑であり、ウルフ条件にもとづく勾配降下法よりもアルミホ条件に基づいた値のほうがより良い理論的保証がある（Backtracking line searchの"Upper bound for learning rates"節および"Theoretical guarantee"節を参照）。

参考文献

• テンプレート:Cite book
• テンプレート:Cite book

関連項目

• テンプレート:仮リンク