直線探索

最適化問題において、直線探索は、目的関数 $f:\mathbb R^n\to\mathbb R$ の極小値 $\mathbf{x}^*$ を求めるための2つの基本的な反復的アプローチのうちの一つである。他方は信頼範囲である。

直線探索のアプローチでは、最初に目的関数 $f$ の値が小さくなる降下方向を求め、次に、その方向に $\mathbf{x}$ をどのくらい動かすかを表すステップサイズを計算する。降下方向を求める方法は、勾配降下法、ニュートン法、準ニュートン法など、数多く存在する。ステップサイズは厳密に求める方法と近似的に求める方法がある。

直線探索の使用例

次の勾配法の例は、第4ステップで直線探索を用いている。

1. 反復カウンターを $\displaystyle k=0$ とする。最小値の初期推定値を $\mathbf{x}_0$ とする。
2. 以下を反復する:
3.     降下方向 $\mathbf{p}_k$ を計算する。
4.     $h(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{p}_k)$ を $\alpha\in\mathbb R_+$ 上で最小化するような $\displaystyle \alpha_k$ を決定する。
5.     $\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{p}_k$ 、 $\displaystyle k=k+1$ と更新する。
6. $\|\nabla f(\mathbf{x}_k)\|$ が十分小さくなるまで続ける。

第4ステップにおいては、$h'(\alpha_k)=0$ を解いて h の厳密な最小値を求める方法と、十分な減少が得られればよいとして大まかに最小化する方法がある。前者の例としては共役勾配法がある。後者は数多くの方法があるが、例えばバックトラック法やWolfe条件を用いた方法がある。

他の最適化法と同様に、直線探索は局所最小値を脱出するために焼きなまし法と組み合わせることができる。

アルゴリズム

直接探索法

この方法では、最初に最小値を囲むような2点x₁、x₂を決めなければならない。次に、この区間を内点 x₃、x₄ で分割し、それぞれの点で $f(x)$ を計算する。そして、x₁、x₂のうち、x₃、x₄で目的関数が大きい方に隣接しているものを除去する。これ以降のステップでは、各ステップで1つの内点のみを加えていけばよい。区間を分割する方法は数多くあるが、黄金分割探索は特にシンプルで効果的である。黄金分割探索では、区間の比率はどのステップでも一定である。

$\frac{1}{\phi}(x_2-x_1)=x_4-x_1=x_2-x_3=\phi(x_2-x_4)=\phi(x_3-x_1)=\phi^2(x_4-x_3)$ where $\phi=\frac{1}{2}(1+\sqrt 5) \approx 1.618$