直線探索

直線探索（ちょくせんたんさく、英: line search）は、連続最適化問題において、目的関数 ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ の極小値 ${\displaystyle \mathbf {x} ^{*}}$ を求めるための2つの基本的な反復的アプローチのうちの一つである。もう一つの基本的な反復的アプローチの方法は信頼領域である。

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

直線探索の主な使用例

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

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

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

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

アルゴリズム

直接探索法

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

${\displaystyle {\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 ${\displaystyle \phi ={\frac {1}{2}}(1+{\sqrt {5}})\approx 1.618}$

脚注

1. ^ Box, M. J.; Davies, D.; Swann, W. H. (1969). Non-Linear optimisation Techniques. Oliver & Boyd 

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）