4.2. Armijo条件・Wolfe条件

はじめに

最急降下法の節ではステップサイズ$t ^ k$をどう定めるかについては言及しなかった。実際、

4. 直線探索法

で解説した通り$t ^ k$の決め方については複数の選択肢があるが、いずれも原始的な方法である。

ここでは直線探索法の収束性を示すのによく用いられる Armijo 条件 と Wolfe 条件について解説する。

Armijo条件

Armijo 条件を満たす限り更新のたびに目的関数は単調減少することが保証される。また Armijo 条件はチェックが簡単で、$m ^ k$に降下方向を用いる限りステップサイズ$t \to 0$の極限で必ず満たされるので、実際にアルゴリズムを実装するときも現在の$t$をステップサイズ$t ^ k$として採用してよいかを判断する重要な指標になる。

Armijo 基準はステップサイズの上限を定める条件とみなせる。

Wolfe条件

Armijo 条件はステップサイズの上限を定めるものの下限についてはなんら言及していない。Armijo 条件は十分に小さい$t$を選べば必ず満たされるので、アルゴリズムは可算無限回のイテレーションでも極値へ到達しないような非常に小さい$t$をステップサイズに選択し続けるかもしれない。この不都合を解消するために、Armijo 条件に加えてステップサイズの下限を定める Wolfe 基準を追加したのが Wolfe 条件である。

Wolfe 条件を満たす更新を繰り返すことで、最急降下法をはじめとして共役勾配法や準ニュートン法など、多くの勾配法のアルゴリズムが高々可算無限回の更新で極値に収束することを示せる。

Wolfe 基準はステップサイズの下限を定める条件とみなせる。

実際にアルゴリズムを実装するとき、Armijo 条件と Wolfe 条件を同時に満たす点を見つけるのは困難である。Armijo 条件は$t$を小さくしていけば必ずどこかでは満たされるが、Wolfe 条件はどこで満たされるか見当もつかないためである。

強Wolfe条件

Wolfe 基準は勾配が単調増加することを要請するので、もともと負の大きい値をとる勾配が更新のたびに 0 に近づくことを期待している。しかし Wolfe 基準は勾配が大きな正の値をとることに関してはなんら制約を設けていないので、アルゴリズムは極値へ収束しないような振動する点列を生成するかもしれない。この不都合を解消するために、Wolfe 基準を絶対値による制約に変更して制約を強めたのが強 Wolfe 条件である。