直線探索 (数理計画における)

【ちょくせんたんさく (line search)】

関数 $f(x)$ を最小化する解法の大域的収束性を実現するための補助手段の1つ, 1次元探索ともいう. $k$ 回目の反復において近似解 $x_k$ と関数値を下げる探索方向 $d_k$ とが与えられたとき, $d_k$ 方向で関数値を減少($f(x_k+\alpha_kd_k)<f(x_k)$)させるステップ幅 $\alpha_k\in R$ を求める作業を直線探索という. 関数値の減少に関する代表的な基準としてアルミホ基準やウルフ基準がある. 特に, 探索方向で $f(x)$ の最小値を与えるステップ幅を求めることを正確な直線探索という.