ウルフ条件

非制限最適化問題において、ウルフ条件（ウルフじょうけん、英: Wolfe conditions）とは、非厳密直線探索を行ううえで用いられる一連の不等式をいう。特に準ニュートン法を行う際によく用いられる。1969年にフィリップ・ウルフが初めて発表した。

ある滑らかな関数$f\colon \mathbb {R} ^{n}\to \mathbb {R}$について非制限最適化問題$$\min _{x}f({\boldsymbol {x}})$$を解く際、近似的な部分問題$$\min _{\alpha }f({\boldsymbol {x}}_{k}+\alpha {\boldsymbol {p}}_{k})$$を解くことがしばしばある。ここでx_kは現状の最適推定解、${\boldsymbol {p}}_{k}\in \mathbb {R} ^{n}$は探索方向、$\alpha \in \mathbb {R}$はステップ長である。

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

アルミホ条件と曲率条件

あるステップ長α_kがウルフ条件を満たすとは、探索方向p_kが与えられたものとして以下の2つの不等式がなりたつことをいう。

1. $f({\boldsymbol {x}}_{k}+\alpha _{k}{\boldsymbol {p}}_{k})\leq f({\boldsymbol {x}}_{k})+c_{1}\alpha _{k}{\boldsymbol {p}}_{k}^{\top }\nabla f({\boldsymbol {x}}_{k})$
2. $-{\boldsymbol {p}}_{k}^{\top }\nabla f({\boldsymbol {x}}_{k}+\alpha _{k}{\boldsymbol {p}}_{k})\leq -c_{2}{\boldsymbol {p}}_{k}^{\top }\nabla f({\boldsymbol {x}}_{k})$

ここで、0 < c₁ < c₂ < 1である(不等式iiを評価する際、たとえば最急降下法の場合は${\boldsymbol {p}}_{k}=-\nabla f({\boldsymbol {x}}_{k})$、ニュートン法の場合は${\boldsymbol {p}}_{k}=-{\boldsymbol {H}}^{-1}\nabla f({\boldsymbol {x}}_{k})$でHが正定値行列であるため${\boldsymbol {p}}_{k}^{\top }\nabla f({\boldsymbol {x}}_{k})<0$が成り立つことに留意が必要である)。

c₁はとても小さく、c₂はそれよりもかなり大きくとることが多い。ノセダルとライトはニュートン法および準ニュートン法についてはc₁ = 10⁻⁴, c₂ = 0.9、非線形共役勾配法についてはc₂ = 0.1を例として与えている。不等式iはアルミホ条件（英: Armijo condition）と呼ばれ、不等式iiは曲率条件と呼ばれる。不等式iはステップ長α_kがfを「十分に」減少させることを、iiは勾配が十分に減少したことを保証する。条件iおよびiiはステップ長の上限と下限をそれぞれあたえるものと解釈できる。

強いウルフ条件

方向p_kに制限した一変数関数φ(α) = f(x_k+α_kp_k)を考える。ウルフ条件はφの最適点からは遠いステップ長を与える場合がある。曲率条件を次のように変更したとする。

3. $\left|{\boldsymbol {p}}_{k}^{\top }\nabla f({\boldsymbol {x}}_{k}+\alpha _{k}{\boldsymbol {p}}_{k})\right|\leq c_{2}\left|{\boldsymbol {p}}_{k}^{\top }\nabla f({\boldsymbol {x}}_{k})\right|$

iおよびiiiは強いウルフ条件と呼ばれ、α_kをφの臨界点付近に制限する。

理論的根拠

最適化アルゴリズムにウルフ条件を課す主な理由は、勾配がゼロに収束することを保証するためである。特に、p_kと勾配との方向余弦$$\cos \theta _{k}={\frac {\nabla f(\mathbf {x} _{k})^{\mathrm {T} }\mathbf {p} _{k}}{\|\nabla f(\mathbf {x} _{k})\|\|\mathbf {p} _{k}\|}}$$がゼロから遠くかつ条件iおよびiiが満たされる場合、$\nabla f(\mathbf {x} _{k})\rightarrow 0$が成り立つ。

もうひとつの動機は、${\boldsymbol {p}}_{k}=-B_{k}^{-1}\nabla f({\boldsymbol {x}}_{k})$のように方向を求める準ニュートン法の場合、行列B_kをBFGS法やDFP法で更新する、B_kが正定値かつiおよびiiが成り立つならばB_k+1も正定値となる。

注意

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

関連項目

• バックトラッキング直線探索

参照文献

• “Line Search Methods”. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. (2006). pp. 30–32. doi:10.1007/978-0-387-40065-5_3. ISBN 978-0-387-30303-1 
• “Quasi-Newton Methods”. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. (2006). pp. 135–163. doi:10.1007/978-0-387-40065-5_6. ISBN 978-0-387-30303-1