4. 直線探索法

2020/1/6公開

直線探索法

直線探索法（line search method）は、現在の点$x _ {(k)} \in \mathbb{R} ^ n$から$m _ {(k)} \in \mathbb{R} ^ n$により方向が定められた$t \in \mathbb{R}$を媒介変数とする直線$x _ {(k)} + t m _ {(k)}$を探索直線として、目的関数$f \colon \mathbb{R} ^ n \to \mathbb{R}$の探索直線上における極値への更新を繰り返すことで最適解へ近づいていく手法の総称である。探索方向$m _ {(k)}$に目的関数の勾配$\operatorname{grad} f(x _ {(k)})$の情報を用いる場合は勾配法（gradient descent）ともいう。

すなわち、アルゴリズムとしてはまず現在の点$x _ {(k)}$から更新方向$m _ {(k)}$を定め、次に

$$\frac{d}{dt} f (x _ {(k)} + t m _ {(k)}) = 0 \tag{4.1}$$

を満たす$t$を見つけて$t _ {(k)}$とおき、

$$x _ {(k+1)} = x _ {(k)} + t _ {(k)} m _ {(k)}$$

と更新することを繰り返すことになる。この$t _ {(k)}$を更新のステップサイズ（step size）という。

現実問題として (4.1) 式を満たす$t$を見つけること自体も$t$に関する最適化問題になっているので、(4.1) 式を満たす$t$を見つけるのは難しい場合がある。たとえば目的関数$f$を評価するのに時間がかかるような問題では厳密に$t$を求めるのは困難である。

ステップサイズ$t$を厳密に求める直線探索法を厳密直線探索法という。厳密直線探索法には

• 黄金分割探索法

• セカント法（割線法）

などがある。

しかし、適当な$t \neq 0$を選んで点$x ^ \prime = x _ {(k)} + t m _ {(k)}$を考えたとき、点$x ^ \prime$における探索方向$m ^ \prime$は一般に$m _ {(k)}$とは一致しない。たとえば最急降下法では

$$m _ {(k)} = - \operatorname{grad} f(x _ {(k)})$$

によって探索方向を定義するが、一般に

$$- \operatorname{grad} f (x ^ \prime) \neq - \operatorname{grad} f (x _ {(k)})$$

である。つまり (4.1) 式を満たす$t$を探す間にも探索すべき方向は刻一刻と変化するから、実用上はステップサイズ$t _ {(k)}$を厳密に求めてもあまり意味がない。

実際、理論的にもステップサイズはあとで解説する Armijo 条件や Wolfe 条件を満たしていれば収束が保証される場合が多い。Armijo 条件を満たす点を探すには

• バックトラック法（backtracking）

がある。

探索方向に勾配を利用すると、勾配は最適解の付近ではそのノルムが 0 に近づくという性質があるから、実用上は

• ステップサイズを小さい定数にする

• ステップサイズを単調減少させる

といった方法でも十分であり、これらの手法もよく用いられる。

しかしその一方で、ステップサイズを

• 小さすぎる定数にする$\Rightarrow$収束するまでに非常に時間がかかる

• 大きすぎる定数にする$\Rightarrow$アルゴリズムが発散/振動する

• 単調減少のスケジュールがうまくない$\Rightarrow$収束までに時間がかかったり発散/振動したりする

といった問題が常につきまとうのも事実であり、ステップサイズのチューニングに時間がかかることもある。

ステップサイズの決定は最適化アルゴリズムの実行時間や収束にクリティカルに影響する重要なパラメータだが、大抵の場合は人間が調整するハイパーパラメータとして扱われ、勘、経験、試行錯誤に頼って決められる。ステップサイズを決定するための方法論は現代においても未熟である。

参考文献

1. 『数理計画法の基礎』http://ocw.nagoya-u.jp/files/38/chap_3_book.pdf