直線探索法#
読み: ちょくせんたんさくほう
英名: Line Search Method
無制約の非線形計画問題に対する反復法.
\(x \in \mathbb{R}^n\) に対し,\(f \colon \mathbb{R}^n \to \mathbb{R}\) を最小化するような点列 \(\{ x_n \} \subset \mathbb{R}^n\) を考える. 現在の点 \(x_k \in \mathbb{R}^n\) に対する関数 \(f\) の降下方向を \(d_k \in \mathbb{R}^n\) とし, それを基にステップ幅 \(\alpha_k \in \mathbb{R}\) を \(\alpha_k = \mathop{\mathrm{argmin}}\limits_{\alpha > 0}{\{ f(x_k + \alpha d_k) \}}\) により求め,次の点を \(x_{k+1} = x_k + \alpha_k d_k\) と定める手法である.
なお,上記式により求める手法は正確な直線探索だが, 緩和された直線探索法として,Armijo 条件等の基準も存在する.
Nuorium Optimizer では,非線形計画問題の求解に対し,直線探索法を利用した内点法のアルゴリズムが存在する.
関連
参考文献
[1]
矢部博. 工業基礎 最適化とその応用. 数理工学社, 2006.