直線探索

直線探索とは

直線探索は、連続最適化問題において、目的関数 \( f: \mathbb{R}^n \to \mathbb{R} \) の極小値 \( \mathbf{x}^ \) を求めるための基本的な反復的アプローチの一つです。もう一つの主要なアプローチは信頼領域法です。

直線探索では、まず目的関数 \( f \) の値が小さくなる降下方向を探索します。次に、その方向に解 \( \mathbf{x} \) をどれだけ移動させるかを示すステップサイズを計算します。このステップサイズを用いて解を更新する方法には、最急降下法、ニュートン法、準ニュートン法など、様々なものが存在します。ステップサイズの決定には、厳密な解を求める方法と、近似的に求める方法があります。

直線探索の主な手順

以下は、勾配法における直線探索の典型的な使用例です。

1. 初期化: 反復回数カウンター \( k \) を0とし、最小値の初期推定値 \( \mathbf{x}_0 \) を設定します。
2. 反復処理: 以下を繰り返します。
降下方向 \( \mathbf{p}_k \) を計算します。
\( h(\alpha) = f(\mathbf{x}_k + \alpha \mathbf{p}_k) \) を \( \alpha \in \mathbb{R}_+ \) の範囲で最小化する \( \alpha_k \) を決定します。
解を \( \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k \) 、 \( k = k+1 \) と更新します。
3. 終了判定: \( \|
abla f(\mathbf{x}_k)\| \) が十分に小さくなるまで反復を続けます。

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

他の最適化手法と同様に、直線探索は局所最小値から脱出するために焼きなまし法などの手法と組み合わせて使用されることがあります。

アルゴリズム

直接探索法

直接探索法では、最初に最小値を含む区間 \( [x_1, x_2] \) を決定します。次に、この区間を内点 \( x_3, x_4 \) で分割し、各点での目的関数 \( f(x) \) の値を計算します。そして、\( x_1 \) と \( x_2 \) のうち、\( x_3 \) と \( x_4 \) で目的関数値が大きい方に隣接する点を削除します。以降のステップでは、各ステップで1つの内点を追加していくことで探索を進めます。

区間の分割方法には様々な手法がありますが、黄金分割探索はシンプルで効果的な方法の一つです。黄金分割探索では、区間の比率がどのステップでも一定に保たれます。

黄金分割探索における区間の比率は以下のようになります。

\( \frac{1}{\varphi} (x_2 - x_1) = x_4 - x_1 = x_2 - x_3 = \varphi (x_2 - x_4) = \varphi (x_3 - x_1) = \varphi^2 (x_4 - x_3) \)

ここで、\( \varphi \) は黄金比であり、その値は \( \varphi = \frac{1}{2} (1 + \sqrt{5}) \approx 1.618 \) です。

まとめ

直線探索は、最適化問題において、効率的に解を探索するための重要な手法です。適切なステップサイズの決定と探索方法の選択が、アルゴリズムの性能に大きく影響します。様々な最適化アルゴリズムと組み合わせて利用することで、より効率的な解の探索が可能になります。

もう一度検索