直線探索のソースを表示

{{出典の明記|date=2015年11月}}
'''直線探索'''（ちょくせんたんさく、{{lang-en-short|line search}}）は、連続[[最適化問題]]において、目的関数 <math>f:\mathbb R^n\to\mathbb R</math> の[[極値|極小値]] <math>\mathbf{x}^*</math> を求めるための2つの基本的な反復的アプローチのうちの一つである。もう一つの基本的な反復的アプローチの方法は[[信頼領域]]である。

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

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

# 反復カウンターを <math>\displaystyle k=0</math> とする。最小値の初期推定値を <math>\mathbf{x}_0</math> とする。
# 以下を反復する:
# &nbsp;&nbsp;&nbsp;&nbsp;降下方向 <math>\mathbf{p}_k</math> を計算する。
# &nbsp;&nbsp;&nbsp;&nbsp;<math>h(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math> を <math>\alpha\in\mathbb R_+</math> 上で最小化するような <math>\displaystyle \alpha_k</math> を決定する。
# &nbsp;&nbsp;&nbsp;&nbsp;<math>\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{p}_k</math> 、 <math>\displaystyle k=k+1</math> と更新する。
# <math>\|\nabla f(\mathbf{x}_k)\|</math> が十分小さくなるまで続ける。

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

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

==アルゴリズム==
=== 直接探索法 ===
この方法では、最初に最小値を囲むような2点''x''<sub>1</sub>、''x''<sub>2</sub>を決めなければならない。次に、この区間を内点 ''x''<sub>3</sub>、''x''<sub>4</sub> で分割し、それぞれの点で <math>f(x)</math> を計算する。そして、''x''<sub>1</sub>、''x''<sub>2</sub>のうち、''x''<sub>3</sub>、''x''<sub>4</sub>で目的関数が大きい方に隣接しているものを除去する。これ以降のステップでは、各ステップで1つの内点のみを加えていけばよい。区間を分割する方法は数多くある<ref>{{Cite book|first1=M. J. |last1=Box|first2=D. |last2=Davies |first3=W. H. |last3=Swann|title=Non-Linear optimisation Techniques|publisher= Oliver & Boyd|year= 1969}}</ref>が、[[黄金分割探索]]は特にシンプルで効果的である。黄金分割探索では、区間の比率はどのステップでも一定である。
:<math>\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)</math> where <math>\varphi=\frac{1}{2}(1+\sqrt 5) \approx 1.618</math>

==脚注==
<references />

{{最適化アルゴリズム}}
{{DEFAULTSORT:ちよくせんたんさく}}
[[Category:最適化アルゴリズム]]
[[Category:数学に関する記事]]