直線探索法

はじめに

以下の最急降下法において、 $\alpha$ を固定するのではなく、ざっくり求めようというのが本記事の趣旨です。

$\begin{eqnarray} {\bf x}^{(k+1)}={\bf x}^{(k)}-\alpha\nabla f({\bf x}^{(k)})\tag{1} \end{eqnarray}$

関数 $f:\mathbb{R}^n\rightarrow\mathbb{R}$ の最小化アルゴリズムにおいて、点 ${\bf x}\in\mathbb{R}^n$ を $\bf d$ 方向に更新することを考えます。
このとき、1変数関数 $\phi(\alpha)=f({\bf x}+\alpha{\bf d}),\alpha > 0$ を扱うことになります。
$\phi'(0)<0$ を満たすとします。( ${\bf d}=-\nabla f$ の場合を考えればイメージしやすいと思います。)

目標は $\phi(0)$ よりも十分小さな関数値 $\alpha$ を求めることです。
そのための計算法を直線探索法といいます。

直線探索において、関数値が十分に減少したかを判定するための条件がいくつかあるので、紹介します。

アルミホ条件

$c_1\in(0,1)$ として、

$\begin{eqnarray} \phi(\alpha)\leq\phi(0)+c_1\alpha\phi'(0)\tag{2} \end{eqnarray}$

を満たす $\alpha$ を選択します。
下図にイメージを記します。

ウルフ条件

アルミホ条件では $\alpha$ が非常に小さな値をとることもあります。
十分な大きさのステップ幅を保証するために、ウルフ条件ではアルミホ条件に加えて、
勾配が $\phi'(0)$ より十分に $0$ に近いことを要請します。

$\begin{eqnarray} &&\phi(\alpha)\leq\phi(0)+c_1\alpha\phi'(0)\tag{3}\\ &&\phi'(\alpha)\geq c_2\phi'(0)\tag{4} \end{eqnarray}$

ここで、 $0 < c_1 < c_2 < 1$ とします。
下図にイメージを記します。

強ウルフ条件

ウルフ条件では、 $\phi'(\alpha)$ の値が正の大きな値をとることがあります。
これを防ぐために、ウルフ条件の $(4)$ を

$\begin{eqnarray} |\phi'(\alpha)|\leq |c_2\phi'(0)|\tag{5} \end{eqnarray}$

で置き換えた条件を用いることがあります。

ゴールドシュタイン条件

ウルフ条件とは別の基準で、 $\alpha$ が小さくなりすぎることを防ぎます。

$\begin{eqnarray} \phi(0)+(1-c)\alpha\phi'(0)\leq\phi(\alpha)\leq\phi(0)+c\alpha\phi'(0)\tag{6} \end{eqnarray}$

ここで、 $c\in(0,1/2)$ とします。

バックトラッキング法

$\alpha$ の探索法を工夫することで、 $\alpha$ が小さくなりすぎることを防ぐ事もできます。
$\alpha$ を適当に決めて、アルミホ条件を満たすまで、徐々に小さくしていく手法です。
バックトラッキング法とは、直線探索法専用の言葉ではなく、
一般的な言葉であり「ある与えられた問題の解を求める際、候補となる解を列挙し、効率的・網羅的に正しい解を探索するアルゴリズム」という意味です。

初期化: アルミホ条件の定数 $c_1\in(0,1)$ 、縮小率 $\rho\in(0,1)$ 、初期値 $\alpha > 0$ を設定する。
1. $\alpha$ がアルミホ条件を満たすなら、 $\alpha$ をステップ幅として出力して停止する。
2. $\alpha\leftarrow\alpha\rho$ とする。ステップ1へ戻る。

直線探索を用いる反復法

初期化: 初期解 ${\bf x}_0\in\mathbb{R}^n$ を定める。 $k\leftarrow 0$ とする。
1. 停止条件が満たされるなら、 ${\bf x}_k$ を数値解として出力して停止する。
2. 降下方向を ${\bf d}_k$ に設定する。
3. 関数 $\phi(\alpha)=f({\bf x}_k+\alpha{\bf d}_k),\alpha\geq 0$ に対する直線探索により、ステップ幅 $\alpha_k$ を設定する。
4. ${\bf x}_{k+1}\leftarrow{\bf x}_k+\alpha_k{\bf d}_k$ と更新する。
5. $k\leftarrow k+1$ とする。ステップ1に戻る。