ウルフ条件

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

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

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

アルミホ条件と曲率条件

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

${\displaystyle 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})}$

(i)

${\displaystyle -{\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})}$

(ii)

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

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

強いウルフ条件

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

${\displaystyle \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|}$

(iii)

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

理論的根拠

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

また、準ニュートン法を用いて${\displaystyle {\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"節を参照）。