ウルフ条件

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

ある滑らかな関数  について無制約最適化問題  を解く際、近似的な部分問題  を解くことがしばしばある。ここで  は現在の反復における最適推定解、 は探索方向、 はステップ長である。

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

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

ここで、 である（不等式を評価する際、たとえば最急降下法の場合は 、ニュートン法の場合は  で  が正定値行列であるため  が成り立つことに留意する）。

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

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

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

 理論的根拠 
最適化アルゴリズムにウルフ条件を課す主な理由は、勾配がゼロに収束することを保証するためである。特に、 と勾配との方向余弦  がゼロから遠くかつ条件およびが満たされる場合、 が成り立つ。

また、準ニュートン法を用いて のように探索方向を決めるとき、行列  をBFGS法やDFP法で更新する場合、 が正定値かつおよびが成り立つならば  も正定値となるということも理由としてあげられる。

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

 脚注 

 注釈 

 出典 

 参考文献 



 関連項目 


Category:最適化
Category:数学に関する記事