読む編集履歴表示

ウルフ条件

ウィキペディアから、無料の百科事典

この項目「ウルフ条件」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en: Wolfe conditions）
修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2024年8月）

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

ある滑らかな関数 $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つの不等式が成り立つことをいう。

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

強いウルフ条件

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

$\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"節を参照）。

脚注

[脚注の使い方]

注釈

↑ 英: Armijo condition

出典

↑ Wolfe, P. (1969). “Convergence Conditions for Ascent Methods”. SIAM Review 11 (2): 226–235. doi:10.1137/1011036. JSTOR 2028111.
↑ Wolfe, P. (1971). “Convergence Conditions for Ascent Methods. II: Some Corrections”. SIAM Review 13 (2): 185–188. doi:10.1137/1013035. JSTOR 2028821.
↑ Nocedal, Jorge; Wright, Stephen (1999). Numerical Optimization. p. 38
↑ 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.

参考文献

“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

関連項目

バックトラッキング直線探索（英語版）

数理最適化 • 最適化問題 : メソッド • ヒューリスティック

非線形（無制約）

… 関数　

勾配法

収束性	信頼領域ウルフ条件
準ニュートン法	BFGS法ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法
その他の求解法	ガウス・ニュートン法最急降下法（確率的）レーベンバーグ・マーカート法共役勾配法（非線形共役勾配法）打ち切りニュートン法ドッグレッグ法鏡像座標バルジライ・ボールウェイン法

… ヘッセ行列

最適化におけるニュートン法

非線形（制約付き）

一般	バリア関数ペナルティ関数法
微分可能	ラグランジュの未定乗数法拡張ラグランジュ関数法逐次二次計画法逐次線形計画法

凸最適化

凸最小化

線形および
二次

内点法	アフィンスケーリング法カーマーカーの射影変換法メロートラの予測子修正子法
基底-交換	単体法改訂単体法十文字法レムケの相補掃き出し法
その他	カチヤンの楕円体法有効制約法列生成法ベンダーズ分解法

組合せ最適化

系列範例
(Paradigms)

グラフ理論

最小全域木	ブルーフカ法クラスカル法プリム法
最短経路問題	ベルマン–フォード法ダイクストラ法ワーシャル–フロイド法ジョンソン法

ネットワークフロー
(最大流問題)

メタヒューリスティクス

カテゴリ（最適化 • アルゴリズム） • ソフトウェア