ライン検索

最適化において、直線探索は目的関数の局所的最小値を見つけるための基本的な反復アプローチです。まず、目的関数が縮小される降下方向を見つけ、次にその方向に沿ってどれだけ移動するかを決定するステップ サイズを計算します。降下方向は、勾配降下法や準ニュートン法など、さまざまな方法で計算できます。ステップ サイズは、正確にまたは不正確に決定できます。 ${\displaystyle \mathbf {x} ^{*}}$ ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle f}$${\displaystyle \mathbf {x} }$

fが 1 次元関数で、単峰性、つまり与えられた区間 [ a , z ] 内に 1 つの極小値x * を含むと仮定します。これは、 fが [a,x*] 内で厳密に減少し、[x*, z ] 内で厳密に増加することを意味します。この場合、(近似) 最小点を見つける方法はいくつかあります。^{[1] : sec.5}${\displaystyle f:\mathbb {R} \to \mathbb {R} }$

ゼロ階法は関数評価（つまり値オラクル）のみを使用し、導関数は使用しない：^{[1] ：sec.5}

• 三元探索: a < b < c < zとなる2 つの点b、c を選択します。f( b )≤f( c ) の場合、 x* は [ a、c ] の範囲内にある必要があります。f( b )≥f( c ) の場合、 x* は [ b、z ] の範囲内にある必要があります。どちらの場合も、探索間隔をより小さいものに置き換えることができます。間隔の中心に非常に近いb、c を選択した場合、間隔は各反復で約 1/2 縮小しますが、反復ごとに 2 つの関数評価が必要になります。したがって、この方法はの率で線形収束します。パーティション a、b、c、z が 3 つの等しい長さの間隔を持つように b、c を選択した場合、間隔は各反復で 2/3 縮小するため、この方法は の率で線形収束します。${\displaystyle {\sqrt {0.5}}\approx 0.71}$${\displaystyle {\sqrt {2/3}}\approx 0.82}$
• フィボナッチ探索: これは三元探索の変形であり、フィボナッチ数列に基づいて点b、cが選択されます。各反復では、もう一方の点が既に前の区間の終点であったため、関数の評価は 1 回のみ必要です。したがって、この方法は収束率 で線形収束します。${\displaystyle 1/\varphi \approx 0.618}$
• 黄金比探索: これは、黄金比に基づいて点b、cが選択される変形です。この場合も、各反復で必要な関数評価は 1 回のみで、この方法は速度 で線形収束します。この比率は、ゼロ次法の中で最適です。${\displaystyle 1/\varphi \approx 0.618}$

ゼロ次法は非常に一般的であり、微分可能性や連続性さえも想定しません。

一次法では、fが連続的に微分可能であり、fだけでなくその導関数も評価できると仮定します。^{[1] ：sec.5}

• 二分法は、区間の中心cにおけるfの導関数を計算します。f'(c)=0 の場合、これが最小点です。f'( c )>0 の場合、最小値は [ a、c ] の範囲内にあります。f'( c )<0 の場合、最小値は [ c、z ]の範囲内にあります。この方法は、収束率 0.5 で線形収束します。

曲線フィッティング法は、f が有限次数の多項式などの解析形式を持つと仮定して、超線形収束を達成しようとします。各反復では、 fの値(および場合によってはその導関数) がわかっている「作業点」のセットがあります。これらの点に基づいて、既知の値に適合する多項式を計算し、その最小値を解析的に見つけることができます。最小点は新しい作業点となり、次の反復に進みます: ^{[1] : sec.5}

• ニュートン法は曲線近似法の特殊なケースであり、曲線はfの 1 次導関数と 2 次導関数を使用して構築された 2 次多項式です。この方法が非退化の局所最小値 (= 正の 2 次導関数) に十分近いところから開始された場合、2 次収束します。
• Regula falsiは、関数を 2 次多項式に当てはめる別の方法ですが、同じ点における 1 次導関数と 2 次導関数ではなく、2 点における 1 次導関数を使用します。この方法が非退化局所最小値に十分近いところから開始された場合、次数の超線形収束が起こります。${\displaystyle \varphi \approx 1.618}$
• 3 次近似は、最後の 2 つのポイントでの関数値とその導関数の両方を使用して、3 次多項式に近似します。この方法が非退化の局所最小値に十分近いところから開始された場合、2 次収束します。

曲線フィッティング法は、局所的最小値に十分近いところから開始すると超線形収束しますが、そうでない場合は発散する可能性があります。保護された曲線フィッティング法は、曲線フィッティング法と並行して線形収束法を同時に実行します。各反復で、曲線フィッティング法によって見つかった点が保護法によって維持される間隔に十分近いかどうかを確認します。そうでない場合は、次の反復を計算するために保護法が使用されます。^{[1] : 5.2.3.4}

一般的に、多次元の目的関数 があります。直線探索法では、まず目的関数が縮小される降下方向を見つけ、次にその方向に沿ってどれだけ移動するかを決定するステップ サイズを計算します。降下方向は、勾配降下法や準ニュートン法など、さまざまな方法で計算できます。ステップ サイズは、正確に決定することも、不正確に決定することもできます。以下は、ステップ 5 で直線探索を使用する勾配法の例です。 ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle f}$${\displaystyle \mathbf {x} }$

1. 反復カウンタを設定し、最小値の初期推定を行います。許容値を選択します。${\displaystyle k=0}$${\displaystyle \mathbf {x} _{0}}$${\displaystyle \epsilon }$
2. ループ：
   1. 降下方向 を計算します。${\displaystyle \mathbf {p} _{k}}$
   2. ステップサイズが与えられたときの降下方向の関数値を表す1 次元関数を定義します。${\displaystyle h(\alpha _{k})=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})}$
   3. を最小化する を見つけます。${\displaystyle \displaystyle \alpha _{k}}$${\displaystyle h}$${\displaystyle \alpha _{k}\in \mathbb {R} _{+}}$
   4. 更新し、${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}$${\textstyle k=k+1}$
3. それまで${\displaystyle \|\nabla f(\mathbf {x} _{k+1})\|<\epsilon }$

直線探索ステップ（2.3）では、アルゴリズムは を解くことによってh を 正確に最小化するか、または前述の1次元直線探索法の1つを使用して を近似的に最小化します。また、必ずしも最適値を近似しない​​ hの十分な減少を求めることによって、緩く を解くこともできます。前者の1つの例は共役勾配法です。後者は不正確な直線探索と呼ばれ、バックトラック直線探索やウルフ条件の使用など、さまざまな方法で実行できます。 ${\displaystyle h'(\alpha _{k})=0}$

他の最適化手法と同様に、直線探索をシミュレーテッドアニーリングと組み合わせることで、いくつかの局所的最小値を飛び越えることができるようになります。

• 信頼領域- 局所最小値を見つけるための二重のアプローチ: 最初にステップ サイズを計算し、次に降下方向を決定します。
• グリッド検索
• 学習率
• パターン検索（最適化）
• セカント法

• Dennis, JE Jr.; Schnabel, Robert B. (1983)。「ニュートン法の全体的収束修正」。制約のない最適化と非線形方程式の数値的手法。Englewood Cliffs: Prentice-Hall。pp. 111–154。ISBN 0-13-627216-9。
• Nocedal, Jorge; Wright, Stephen J. (1999)。「ラインサーチ法」。数値最適化。ニューヨーク: Springer。pp. 34–63。ISBN 0-387-98793-2。
• Sun, Wenyu; Yuan, Ya-Xiang (2006)。「Line Search」。最適化理論と方法: 非線形プログラミング。ニューヨーク: Springer。pp. 71–117。ISBN 0-387-24975-3。