ウルフ条件のソースを表示

{{翻訳直後|[[:en:Special:Permalink/1224419897|en: Wolfe conditions]]|date=2024年8月}}

'''ウルフ条件'''（ウルフじょうけん、{{Lang-en-short|Wolfe conditions}}）とは、無制約[[最適化問題]]において非厳密[[直線探索]]を行う際に用いられる一連の[[不等式]]をいう。特に[[準ニュートン法]]を行う際によく用いられる。[[1969年]]に{{仮リンク|フィリップ・ウルフ (数学者)|en|Philip Wolfe (mathematician)|label=フィリップ・ウルフ}}が初めて発表した<ref>{{Cite journal|last=Wolfe|first=P.|year=1969|title=Convergence Conditions for Ascent Methods|journal=[[SIAM Review]]|volume=11|issue=2|pages=226–235|doi=10.1137/1011036|JSTOR=2028111}}</ref><ref>{{Cite journal|last=Wolfe|first=P.|year=1971|title=Convergence Conditions for Ascent Methods. II: Some Corrections|journal=[[SIAM Review]]|volume=13|issue=2|pages=185–188|doi=10.1137/1013035|JSTOR=2028821}}</ref>。

ある[[滑らかな関数]] <math>f\colon\mathbb R^n\to\mathbb R</math> について無制約最適化問題 <math display="block">\min_x f(\boldsymbol{x})</math> を解く際、近似的な部分問題 <math display="block">\min_{\alpha} f(\boldsymbol{x}_k + \alpha \boldsymbol{p}_k)</math> を解くことがしばしばある。ここで {{Mvar|'''x'''<sub>k</sub>}} は現在の反復における最適推定解、<math>\boldsymbol{p}_k \in \mathbb R^n</math> は探索方向、<math>\alpha \in \mathbb R</math> はステップ長である。

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

== アルミホ条件と曲率条件 ==
あるステップ長 {{Mvar|&alpha;<sub>k</sub>}} がウルフ条件を満たすとは、探索方向 {{Mvar|'''p'''<sub>k</sub>}} が与えられたものとして以下の2つの不等式が成り立つことをいう。{{Ordered list|<math>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)</math>|<math>-\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)</math>|list-style-type=lower-roman}} ここで、{{Math|0 < ''c''<sub>1</sub> < ''c''<sub>2</sub> < 1}} である（不等式iiを評価する際、たとえば[[最急降下法]]の場合は <math>\boldsymbol{p}_k = -\nabla f({\boldsymbol{x}}_k)</math>、[[ニュートン法]]の場合は <math>\boldsymbol{p}_k = -\boldsymbol{H}^{-1} \nabla f(\boldsymbol{x}_k)</math> で {{Mvar|'''H'''}} が正定値行列であるため <math>\boldsymbol{p}_k^{\top}\nabla f(\boldsymbol{x}_k) < 0</math> が成り立つことに留意する）。

{{Math|''c''<sub>1</sub>}} は十分に小さく、{{Math|''c''<sub>2</sub>}} は十分に大きくとることが多い。{{仮リンク|ホルヘ・ノセダル|en|Jorge Nocedal|label=ノセダル}}とライトはニュートン法および準ニュートン法については {{Math|1=''c''<sub>1</sub> = 10<sup>&minus;4</sup>, ''c''<sub>2</sub> = 0.9}}、[[非線形共役勾配法]]については {{Math|1=''c''<sub>2</sub> = 0.1}} を例として与えている<ref>{{Cite book |title=Numerical Optimization |last=Nocedal |first=Jorge |author-link=:en:Jorge Nocedal |last2=Wright |first2=Stephen |url=https://books.google.com/books?id=epc5fX0lqRIC&pg=PA38 |year=1999 |page=38}}</ref>。不等式iは'''アルミホ条件'''{{Efn|{{Lang-en-short|Armijo condition}}}}<ref>{{Cite journal|last=Armijo|first=Larry|year=1966|title=Minimization of functions having Lipschitz continuous first partial derivatives|url=http://projecteuclid.org/euclid.pjm/1102995080|journal=Pacific J. Math.|volume=16|issue=1|pages=1–3|doi=10.2140/pjm.1966.16.1}}</ref>と呼ばれ、不等式iiは'''曲率条件'''と呼ばれる。不等式iはステップ長 {{Mvar|&alpha;<sub>k</sub>}} が {{Mvar|f}} を「十分に」減少させることを、iiは勾配が十分に減少したことを保証する。条件iおよびiiはステップ長の上限と下限をそれぞれ与えるものとして解釈することができる。

== 強いウルフ条件 ==
方向 {{Mvar|'''p'''<sub>k</sub>}} に制限した一変数関数 {{Math|1=''&phi;''(''&alpha;'') = ''f''('''''x'''''<sub>''k''</sub>+''&alpha;<sub>k</sub>'''p'''<sub>k</sub>'')}} を考える。ウルフ条件は {{Mvar|&phi;}} の最適点からは遠いステップ長を与える場合がある。曲率条件を次のように変更したとする: {{Ordered list|<math>\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|</math>|list-style-type=lower-roman|start=3}}。iおよびiiiは'''強いウルフ条件'''と呼ばれ、{{Mvar|&alpha;<sub>k</sub>}} を {{Mvar|&phi;}} の[[臨界点 (数学)|臨界点]]付近に制限する。

== 理論的根拠 ==
最適化アルゴリズムにウルフ条件を課す主な理由は、勾配がゼロに収束することを保証するためである。特に、{{Mvar|'''p'''<sub>k</sub>}} と勾配との{{仮リンク|方向余弦|en|Direction cosine|redirect=1}} <math display="block"> \cos \theta_k = \frac {\nabla f(\mathbf{x}_k)^{\mathrm T}\mathbf{p}_k }{\| \nabla f(\mathbf{x}_k)\| \|\mathbf{p}_k\| }</math> がゼロから遠くかつ条件iおよびiiが満たされる場合、<math> \nabla f(\mathbf{x}_k) \rightarrow 0 </math> が成り立つ。

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

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

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
* {{Cite book |doi=10.1007/978-0-387-40065-5_3 |chapter=Line Search Methods |title=Numerical Optimization |series=Springer Series in Operations Research and Financial Engineering |pages=30–32 |year=2006 |isbn=978-0-387-30303-1 }}
* {{Cite book |doi=10.1007/978-0-387-40065-5_6 |chapter=Quasi-Newton Methods |title=Numerical Optimization |series=Springer Series in Operations Research and Financial Engineering |pages=135–163 |year=2006 |isbn=978-0-387-30303-1 }}

== 関連項目 ==
* {{仮リンク|バックトラッキング直線探索|en|Backtracking line search}}

{{最適化アルゴリズム}}

{{DEFAULTSORT:うるふしようけん}}
[[Category:最適化]]
[[Category:数学に関する記事]]