ウルフ条件

制約なし最小化問題において、ウルフ条件は、特に準ニュートン法において不正確な直線探索を実行するための不等式の集合であり、 1969年にフィリップ・ウルフによって初めて発表されました。 ^{[1] [2]}

これらの方法では、 滑らかな を見つけようとします。各ステップでは、多くの場合、 が現在の最善の推測、が検索方向、 がステップ長である サブ問題を近似的に解きます 。$${\displaystyle \min _{x}f(\mathbf {x} )}$$ ${\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} }$$${\displaystyle \min _{\alpha }f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$$${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {p} _{k}\in \mathbb {R} ^{n}}$${\displaystyle \alpha \in \mathbb {R} }$

不正確な直線探索は、目的関数を正確に最小化するのではなく、目的関数を「十分に」削減する許容可能なステップ長を計算する効率的な方法を提供します。直線探索アルゴリズムは、新しい探索方向を見つける前に、推測された に対する要件として Wolfe 条件を使用できます。 ${\displaystyle \alpha}$${\displaystyle \alpha \in \mathbb {R} ^{+}}$${\displaystyle \alpha}$${\displaystyle \mathbf {p} _{k}}$

次の 2 つの不等式が成り立つ場合、ステップ長は方向 に制限されたWolfe 条件を満たすと言われます。 ${\displaystyle \alpha_{k}}$${\displaystyle \mathbf {p} _{k}}$

となります。(条件 (ii) を調べる際、 が降下方向であることを保証するために、 となる最急降下法の場合と同様に、またはとなるニュートン・ラプソン、つまり となることを思い出してください。ただし は正定値です。) ${\displaystyle 0<c_{1}<c_{2}<1}$${\displaystyle \mathbf {p} _{k}}$${\displaystyle \mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k})<0}$${\displaystyle \mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$${\displaystyle \mathbf {p} _{k}=-\mathbf {H} ^{-1}\nabla f(\mathbf {x} _{k})}$${\displaystyle \mathbf {H} }$

${\displaystyle c_{1}}$は通常、非常に小さくなるように選ばれるのに対し、 は非常に大きく選ばれます。Nocedalと Wright は、ニュートン法または準ニュートン法、および非線形共役勾配法 の と の例としての値を示しています。 [ 3 ]不等式i ^)はアルミヨの法則^[4]として知られ、ii) は曲率条件として知られています。i) はステップ長が「十分に」減少することを保証し 、ii) は傾斜が十分に小さくなったことを保証します。条件 i) と ii) は、それぞれ許容されるステップ長の値の上限と下限を提供するものと解釈できます。 ${\displaystyle c_{2}}$${\displaystyle c_{1}=10^{-4}}$${\displaystyle c_{2}=0.9}$${\displaystyle c_{2}=0.1}$${\displaystyle \alpha _{k}}$${\displaystyle f}$

方向に制限された一変量関数を と表す。Wolfe 条件により、ステップ長の値が の最小値に近くない可能性がある。曲率条件を次のように変更すると、 ${\displaystyle \varphi }$${\displaystyle \mathbf {p} _{k}}$${\displaystyle \varphi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$${\displaystyle \varphi }$

すると、i) と iii) が一緒になって、いわゆる強い Wolfe 条件を形成し、の臨界点に近づくことになります。 ${\displaystyle \alpha _{k}}$${\displaystyle \varphi }$

最適化アルゴリズムで Wolfe 条件を課す主な理由は、勾配が 0 に収束することを保証するためです。特に、と勾配の 間の角度の余弦 が 0 から離れる方向に制限され、i) および ii) の条件が満たされる場合、 となります。 ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha \mathbf {p} _{k}}$${\displaystyle \mathbf {p} _{k}}$$${\displaystyle \cos \theta _{k}={\frac {\nabla f(\mathbf {x} _{k})^{\mathrm {T} }\mathbf {p} _{k}}{\|\nabla f(\mathbf {x} _{k})\|\|\mathbf {p} _{k}\|}}}$$${\displaystyle \nabla f(\mathbf {x} _{k})\rightarrow 0}$

準ニュートン法の場合の追加の動機は、行列がBFGSまたはDFP式によって更新されるの場合、 が正定値である場合、 ii) も正定値であることを意味することです。 ${\displaystyle \mathbf {p} _{k}=-B_{k}^{-1}\nabla f(\mathbf {x} _{k})}$${\displaystyle B_{k}}$${\displaystyle B_{k}}$${\displaystyle B_{k+1}}$

Wolfe の条件は Armijo の条件よりも複雑であり、Armijo の条件に基づく勾配降下アルゴリズムは Wolfe の条件に基づくアルゴリズムよりも優れた理論的保証を備えています ( 「バックトラッキング ライン検索」の記事 の「学習率の上限」と「理論的保証」のセクションを参照してください)。

• バックトラックライン検索

• 「ラインサーチ法」。数値最適化。Springer オペレーションズリサーチおよび金融工学シリーズ。2006 年。30～32 ページ。doi : 10.1007/978-0-387-40065-5_3。ISBN 978-0-387-30303-1。
• 「準ニュートン法」。数値最適化。Springer オペレーションズ リサーチおよび金融工学シリーズ。2006 年。pp. 135–163。doi : 10.1007 /978-0-387-40065-5_6。ISBN 978-0-387-30303-1。