非厳密直線探索の終了条件。

\[ \boldsymbol{x}_{k+1}\colon=\boldsymbol{x}_k+\alpha_k\boldsymbol{p}_k\]

なる反復法において探索方向\(\boldsymbol{p}_k\)を決めた後ステップサイズ\(\alpha_k\)を決めるために直線探索（Line search）を行う。\(\boldsymbol{p}_k\)が降下方向（固定）とすると\(f(\boldsymbol{x}_k+\alpha\boldsymbol{p}_k)\)の\(\alpha\)に対する値の変化は一例として図のようになる。関数値が停留する点（stationary point）では図にあるような極大、極小、最小値のほかいずれでもない変曲点もありえる。

厳密直線探索では関数値が最小となるような\(\alpha\)を選択するが、非厳密直線探索では特定の条件を満たすような\(\alpha\)をなるべく少ない関数値の評価回数でもって選択し、次のステップに移行する。

Armijo条件（アルミホ条件）

探索方向\(\boldsymbol{p}_k\)の直線上で関数値が十分に減少することを要求する条件。

sufficient decrease condition: SD

\[ f(\boldsymbol{x}_k+\alpha \boldsymbol{p}_k)\le f(\boldsymbol{x}_k)+c_1\alpha\nabla f_k^\top \boldsymbol{p}_k\]

これをsufficient decreaseの略でSDとかく。アルミホ条件=SDである。\(c_1\in(0,1)\)によって要求する減少量をコントロールする。大きい\(c_1\)ほど大きな減少を要求する。

\(c_1\)をいろいろ変化したときの右辺の様子を示した。実際には使わないが\(c_1=1\)​の場合は\(\alpha=0\)における接線になる。\(c_1\)を小さくするにしたがって不等式を満たすような\(\alpha\)の区間が現れてくる。

典型的には\(c_1=10^{-4}\)などのごく小さい値が使われるとのこと。この場合はスケールにもよるが今の関数値より小さければ何でもいいという意味の条件になる。

Wolfe条件（ウルフ条件）

アルミホ条件だけでは単に\(\alpha\)をいくらでも小さくすれば（\(\boldsymbol{p}_k\)が降下方向なら）条件を満たしてしまうため、毎回そのような小さすぎる\(\alpha\)が選択されてしまうと最適化の効率が上がらない。そこで以下の条件を考える。

curvature condition: C

\[ \nabla f(\boldsymbol{x}_k+\alpha\boldsymbol{p}_k)^\top\boldsymbol{p}_k\ge c_2\nabla f_k^\top\boldsymbol{p}_k\]

これをcurvatureの略でCとかく。ただし\(c_2\in(c_1,1)\)。右辺は\(\nabla f_k\equiv \nabla f(\boldsymbol{x}_k)\)という略記を使っている。左辺は関数値を\(\alpha\)の関数としてみたときにそれを\(\alpha\)で微分したもの。

\[ \begin{align}\phi(\alpha)&=\nabla f(\boldsymbol{x}_k+\alpha\boldsymbol{p}_k)\\\phi'(\alpha)&=\nabla f(\boldsymbol{x}_k+\alpha\boldsymbol{p}_k)^\top\boldsymbol{p}_k\end{align}\]

右辺は\(\alpha=0\)における勾配を定数倍したもの。

\(c_2\)をいろいろ変えたときの右辺と左辺を下の方の図に示した。オレンジのラインが点線より上にある区間が条件Cを満たす区間。これは更新後の点の勾配が今いるところの勾配よりも緩くなっていることを要求している。

このように\(c_2\)が1に近づくにつれて条件を満たすような\(\alpha\)の区間は大きくなる。逆に0に近づくと条件を満たす最も小さい\(\alpha\)は大きくなっていくのでアルミホ条件における小さすぎる\(\alpha\)を回避するような条件となっている。

これを用いたウルフ条件とは

\[ \begin{gather}f(\boldsymbol{x}_k+\alpha\boldsymbol{p}_k)\le f(\boldsymbol{x}_k)+c_1\alpha\nabla f_k^\top\boldsymbol{p}_k\\\nabla f(\boldsymbol{x}_k+\alpha\boldsymbol{p}_k)^\top\boldsymbol{p}_k\ge c_2\nabla f_k^\top\boldsymbol{p}_k\end{gather}\]

をある\(0\lt c_1\lt c_2\lt 1\)について満たすこと。ウルフ条件=SD+Cである。図で言うと先に示した赤塗りの区間と青塗りの区間の共通部分になる。例として\(c_1=0.2, c_2=0.5\)の場合を示す。

強いウルフ条件とは第2式を以下に修正したもののことをいう。

strong curvature condition: SC

\[ |\nabla f(\boldsymbol{x}_k+\alpha\boldsymbol{p}_k)^\top\boldsymbol{p}_k|\le c_2|\nabla f_k^\top\boldsymbol{p}_k|\]

これをstrong curavatureの略でSCとかく。強いウルフ条件=SD+SCである。普通のウルフ条件との違いは勾配が正の方向に急すぎてもいけないという要求があること。同じく\(c_1=0.2, c_2=0.5\)の図を例に取ると下の図で原点対象にもう1本赤い線を引いくとわかりやすい。オレンジの線がこの範囲に入っている区間がSC式を満たす区間である。

これを見てわかるように強いWolfe条件を満たす区間はより狭まった。強いウルフ条件も普通のウルフ条件も第2式は勾配がゼロのところ、すなわち停留点を含むことがわかる。十分小さい\(c_1\)を取っておけば極大を除くことはあっても極小や最小値を条件から除いてしまうことが無いので直線探索の終了条件として（極小や最小な点で終わりたいという）望ましい性質をもっていることがわかる。

似たものにGoldstein条件というものがあるがこちらは常に極小最小点を条件を満たす区間内に含むとは限らない。

Backtrackingアルゴリズム

アルミホ条件SDだけでは小さすぎる\(\alpha\)を毎回選択してしまって最適化の効率が上がらない場合がありえるというところからウルフ条件Cというものを考えた。しかし、単に小さすぎる\(\alpha\)を回避したいだけであれば以下に示すバックトラッキングという方法が使える。

• \(\rho\in(0,1), c_1\in(0,1)\)
• \(\alpha\colon=\) ある大きな値,
• \(f(\boldsymbol{x}_k+\alpha\boldsymbol{p}_k)\le f(\boldsymbol{x}_k)+c_1\alpha\nabla f_k^\top\boldsymbol{p}_k\)を満たすまで以下を行う
  • \(\alpha\colon=\rho\alpha\)
• \(\alpha\)を採用する。

大きい\(\alpha\)から始めてそれを毎回\(\rho\)倍することによって等比数列のように小さくしていく。そのなかで最初にアルミホを満たした\(\alpha\)を採用する。このようにすると小さすぎる\(\alpha\)を毎回選択してしまうということにはならないことが想像できる。最初に選んだ大きな\(\alpha\)がアルミホを満たせば直ちにそれが採用されるし、\(\boldsymbol{p}_k\)が降下方向であるなら最終的に十分小さな\(\alpha\)でもっていずれアルミホは満足される。

ただ、これによっていずれアルミホを満たすことは言えてもウルフを満たすとは言えない（たまたま満たすことは十分に期待されるが）。ウルフ条件を満たすようなステップサイズを探索するにはこれとは違う安直ではないアルゴリズムが必要だ。つづく。

参考文献

Nocedal, Jorge, and Stephen J. Wright. “Numerical optimization” Second Edition (2006). pp.31-37, 3. Line Search Methods - 3.1 Step Length.