直線探索

直線探索（ちょくせんたんさく、）は、連続最適化問題において、目的関数 formula_1 の極小値 formula_2 を求めるための2つの基本的な反復的アプローチのうちの一つである。もう一つの基本的な反復的アプローチの方法は信頼領域である。
直線探索のアプローチでは、最初に目的関数 formula_3 の値が小さくなる降下方向を求め、次に、その方向に formula_4 をどのくらい動かすかを表すステップサイズを計算する。そのステップサイズを用いて、解を求める方法として、最急降下法、ニュートン法、準ニュートン法など、数多く存在する。ステップサイズは厳密に求める方法と近似的に求める方法がある。
直線探索の主な使用例.
次の勾配法の例は、第4ステップで直線探索を用いている。
第4ステップにおいては、formula_14 を解いて "h" の厳密な最小値を求める方法と、十分な減少が得られればよいとして大まかに最小化する方法がある。前者の例としては共役勾配法がある。後者は数多くの方法があるが、例えばバックトラック法やWolfe条件を用いた方法がある。
他の最適化法と同様に、直線探索は局所最小値を脱出するために焼きなまし法と組み合わせることができる。
アルゴリズム.
直接探索法.
この方法では、最初に最小値を囲むような2点"x"1、"x"2を決めなければならない。次に、この区間を内点 "x"3、"x"4 で分割し、それぞれの点で formula_15 を計算する。そして、"x"1、"x"2のうち、"x"3、"x"4で目的関数が大きい方に隣接しているものを除去する。これ以降のステップでは、各ステップで1つの内点のみを加えていけばよい。区間を分割する方法は数多くあるが、黄金分割探索は特にシンプルで効果的である。黄金分割探索では、区間の比率はどのステップでも一定である。