ウルフ条件

ウルフ条件とは

最適化問題、特に非制限最適化問題において、関数の最小値を効率的に見つけるために、ウルフ条件というものが利用されます。これは、非厳密直線探索を行う際に、適切なステップ長を選択するための基準となる一連の不等式です。特に、準ニュートン法のようなアルゴリズムでよく用いられます。

背景

最適化問題では、関数 f(x) の最小値を見つけることが目標となります。この際、現在の推定解 x_k から、探索方向 p_k に沿って、どれだけ進むか（ステップ長 α）を決定する必要があります。厳密に最小化するステップ長を求めることは計算コストが高いため、近似的に「十分に」小さくするステップ長を効率的に見つけることが重要です。ここで、ウルフ条件が役立ちます。

ウルフ条件の内容

ウルフ条件は、以下の二つの不等式で構成されます。あるステップ長 α_k がウルフ条件を満たすとは、以下の二つの不等式が成立することを指します。

1. アルミホ条件 (Armijo condition)

f(x_k + α_k p_k) ≤ f(x_k) + c_1 α_k ∇f(x_k)^T p_k

この条件は、ステップ長 α_k によって関数 f が「十分に」減少することを保証します。ここで、c_1 は非常に小さい正の定数です。

2. 曲率条件

∇f(x_k + α_k p_k)^T p_k ≥ c_2 ∇f(x_k)^T p_k

この条件は、勾配が「十分に」減少したことを保証します。ここで、c_2 は c_1 より大きく、1 より小さい正の定数です。

これらの条件は、ステップ長 α_k の下限と上限をそれぞれ与えるものと解釈できます。

強いウルフ条件

通常のウルフ条件に加えて、曲率条件を以下のように変更した強いウルフ条件も存在します。

3. 強い曲率条件

|∇f(x_k + α_k p_k)^T p_k| ≤ c_2 |∇f(x_k)^T p_k|

この条件は、ステップ長 α_k を関数 φ(α) = f(x_k + α p_k) の臨界点の近くに制限します。これによって、より良いステップ長を選択できる場合があります。

理論的根拠

ウルフ条件を最適化アルゴリズムに課す主な理由は、勾配がゼロに収束することを保証するためです。特に、探索方向 p_k と勾配との方向余弦がゼロから遠く、ウルフ条件が満たされる場合、勾配はゼロに収束します。また、準ニュートン法の場合、行列 B_k を更新する際に、B_k が正定値であり、ウルフ条件が満たされていれば、B_{k+1} も正定値となることが保証されます。

実装における注意点

ウルフ条件は、アルミホ条件よりも複雑であり、実装において注意が必要です。勾配降下法においては、アルミホ条件に基づく直線探索の方がより良い理論的保証を持つ場合があります。ウルフ条件は、特に準ニュートン法のような、より複雑な最適化アルゴリズムでその有用性が発揮されます。

まとめ

ウルフ条件は、非制限最適化問題において、効率的な直線探索を行うための重要なツールです。アルミホ条件と曲率条件の組み合わせにより、適切なステップ長を選択し、最適解への収束を促進します。特に準ニュートン法などのアルゴリズムでは、その安定性と効率性を高めるために欠かせない概念となっています。

関連項目

バックトラッキング直線探索

出典

Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer Series in Operations Research and Financial Engineering.

もう一度検索