コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

ウルフ条件

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

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

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

アルミホ条件と曲率条件

[編集]

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

ここで、0 < c1 < c2 < 1である(不等式iiを評価する際、たとえば最急降下法の場合はニュートン法の場合はHが正定値行列であるためが成り立つことに留意が必要である)。

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

強いウルフ条件

[編集]

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

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

理論的根拠

[編集]

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

もうひとつの動機は、のように方向を求める準ニュートン法の場合、行列BkBFGS法DFP法で更新する、Bkが正定値かつiおよびiiが成り立つならばBk+1も正定値となる。

注意

[編集]

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

関連項目

[編集]

出典

[編集]
  1. ^ Wolfe, P. (1969). “Convergence Conditions for Ascent Methods”. SIAM Review 11 (2): 226–235. doi:10.1137/1011036. JSTOR 2028111. 
  2. ^ Wolfe, P. (1971). “Convergence Conditions for Ascent Methods. II: Some Corrections”. SIAM Review 13 (2): 185–188. doi:10.1137/1013035. JSTOR 2028821. 
  3. ^ Nocedal, Jorge; Wright, Stephen (1999). Numerical Optimization. p. 38. https://books.google.com/books?id=epc5fX0lqRIC&pg=PA38 
  4. ^ Armijo, Larry (1966). “Minimization of functions having Lipschitz continuous first partial derivatives”. Pacific J. Math. 16 (1): 1–3. doi:10.2140/pjm.1966.16.1. http://projecteuclid.org/euclid.pjm/1102995080. 

参照文献

[編集]
  • “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