ドッグレッグ法
ドッグレッグ法（またはパウエルのドッグレッグ法）は、1970年にマイケル・J・D・パウエルによって提案された、非線形最小二乗問題を解くための反復最適化アルゴリズムです。この方法は、レーベンバーグ・マルカート法と同様に、ガウス・ニュートン法と勾配降下法（最急降下法）を組み合わせたものであり、特に信頼領域を明示的に用いる点が特徴です。
ドッグレッグ法では、各反復において、まずガウス・ニュートン法によってステップが計算されます。このステップが事前に設定された信頼領域内にある場合は、そのステップを用いて現在の解が更新されます。一方、ガウス・ニュートン法によるステップが信頼領域の外に出てしまう場合には、最急降下方向に沿った目的関数の最小点（コーシー点）が探索されます。もし、このコーシー点が信頼領域の外側にある場合は、信頼領域の境界まで短縮され、それが新しい解として採用されます。コーシー点が信頼領域内にある場合は、信頼領域の境界と、コーシー点とガウス・ニュートン法によるステップを結ぶ線分（ドッグレッグステップ）との交点が、次の解として採用されます。
このアルゴリズムの名前の由来は、このドッグレッグステップの形状が、ゴルフコースのドッグレッグホールに似ていることにあります。
与えられた関数 \( f_i : \mathbb{R}^n \to \mathbb{R} \) に対して、以下の形式の最小二乗問題を考えます。
\[ F(\boldsymbol{x}) = \frac{1}{2} \|\boldsymbol{f}(\boldsymbol{x})\|^2 = \frac{1}{2} \sum_{i=1}^{m} (f_i(\boldsymbol{x}))^2 \]
パウエルのドッグレッグ法は、この最小二乗問題の最適点 \(\boldsymbol{x}^* = \operatorname{argmin}_{\boldsymbol{x}} F(\boldsymbol{x})\) に収束する点列を、次の更新式を用いて構築します。
\[ \boldsymbol{x}_{k} = \boldsymbol{x}_{k-1} + \delta_{k} \]
各反復におけるステップ \(\delta_k\) は、以下のように計算されます。
ガウス・ニュートン法によるステップは、次のように計算されます。
\[ \boldsymbol{\delta_{\mathrm{gn}}} = -(\boldsymbol{J}^{\top} \boldsymbol{J})^{-1} \boldsymbol{J}^{\top} \boldsymbol{f}(\boldsymbol{x}) \]
ここで、\(\boldsymbol{J} = (\frac{\partial f_i}{\partial x_j})\) はヤコビ行列を表します。
最急降下方向は、次の式で与えられます。
\[ \boldsymbol{\delta_{\mathrm{sd}}} = -\boldsymbol{J}^{\top} \boldsymbol{f}(\boldsymbol{x}) \]
目的関数を最急降下方向に沿って線形化すると、次のようになります。
\[ \begin{aligned} F(\boldsymbol{x} + t\boldsymbol{\delta_{\mathrm{sd}}}) &\approx \frac{1}{2} \|\boldsymbol{f}(\boldsymbol{x}) + t\boldsymbol{J}(\boldsymbol{x})\boldsymbol{\delta_{\mathrm{sd}}}\|^2 \\ &= F(\boldsymbol{x}) + t\boldsymbol{\delta_{\mathrm{sd}}}^{\top} \boldsymbol{J}^{\top} \boldsymbol{f}(\boldsymbol{x}) + \frac{1}{2} t^2 \|\boldsymbol{J}\boldsymbol{\delta_{\mathrm{sd}}}\|^2 \end{aligned} \]
コーシー点におけるパラメータ \(t\) の値は、上記の式を \(t\) で微分してゼロとすることで得られます。その結果、 \(t\) は次のようになります。
\[ t = -\frac{\boldsymbol{\delta_{\mathrm{sd}}}^{\top} \boldsymbol{J}^{\top} \boldsymbol{f}(\boldsymbol{x})}{\|\boldsymbol{J}\boldsymbol{\delta_{\mathrm{sd}}}\|^2} = \frac{\|\boldsymbol{\delta_{\mathrm{sd}}}\|^2}{\|\boldsymbol{J}\boldsymbol{\delta_{\mathrm{sd}}}\|^2} \]
与えられた信頼半径 \(\Delta\) のもとで、パウエルのドッグレッグ法では、更新ステップ \(\delta_k\) を以下のように選択します。
1. ガウス・ニュートンステップ \(\boldsymbol{\delta_{\mathrm{gn}}}\) が信頼領域内にある場合（\(\|\boldsymbol{\delta_{\mathrm{gn}}}\| \le \Delta\) の場合）、ステップは \(\boldsymbol{\delta_{\mathrm{gn}}}\) となります。
2. ガウス・ニュートンステップと最急降下ステップの両方が信頼領域外にある場合（\(\|t\boldsymbol{\delta_{sd}}\| > \Delta\) の場合）、ステップは \( \frac{\Delta}{\|\boldsymbol{\delta_{\mathrm{sd}}}\|}\boldsymbol{\delta_{\mathrm{sd}}}\) となります。
3. ガウス・ニュートンステップが信頼領域の外にあり、かつ最急降下ステップが内側にある場合、ステップは、以下の式を満たす \(s\) を求めたものになります。
\[ t\boldsymbol{\delta_{\mathrm{sd}}} + s(\boldsymbol{\delta_{\mathrm{gn}}} - t\boldsymbol{\delta_{\mathrm{sd}}}) \]
このステップは、信頼領域の境界を満たすように計算されたドッグレッグステップとなります。
ドッグレッグ法は、ガウス・ニュートン法と最急降下法を効率的に組み合わせ、信頼領域の概念を導入することで、非線形最小二乗問題に対する安定した解法を提供します。その反復プロセスは、ゴルフのドッグレッグホールのように、ガウス・ニュートンステップと最急降下ステップを組み合わせて進行し、最適解へと収束していきます。
アルゴリズムの概要
ドッグレッグ法では、各反復において、まずガウス・ニュートン法によってステップが計算されます。このステップが事前に設定された信頼領域内にある場合は、そのステップを用いて現在の解が更新されます。一方、ガウス・ニュートン法によるステップが信頼領域の外に出てしまう場合には、最急降下方向に沿った目的関数の最小点（コーシー点）が探索されます。もし、このコーシー点が信頼領域の外側にある場合は、信頼領域の境界まで短縮され、それが新しい解として採用されます。コーシー点が信頼領域内にある場合は、信頼領域の境界と、コーシー点とガウス・ニュートン法によるステップを結ぶ線分（ドッグレッグステップ）との交点が、次の解として採用されます。
このアルゴリズムの名前の由来は、このドッグレッグステップの形状が、ゴルフコースのドッグレッグホールに似ていることにあります。
定式化
与えられた関数 \( f_i : \mathbb{R}^n \to \mathbb{R} \) に対して、以下の形式の最小二乗問題を考えます。
\[ F(\boldsymbol{x}) = \frac{1}{2} \|\boldsymbol{f}(\boldsymbol{x})\|^2 = \frac{1}{2} \sum_{i=1}^{m} (f_i(\boldsymbol{x}))^2 \]
パウエルのドッグレッグ法は、この最小二乗問題の最適点 \(\boldsymbol{x}^* = \operatorname{argmin}_{\boldsymbol{x}} F(\boldsymbol{x})\) に収束する点列を、次の更新式を用いて構築します。
\[ \boldsymbol{x}_{k} = \boldsymbol{x}_{k-1} + \delta_{k} \]
各反復におけるステップ \(\delta_k\) は、以下のように計算されます。
ガウス・ニュートンステップ
ガウス・ニュートン法によるステップは、次のように計算されます。
\[ \boldsymbol{\delta_{\mathrm{gn}}} = -(\boldsymbol{J}^{\top} \boldsymbol{J})^{-1} \boldsymbol{J}^{\top} \boldsymbol{f}(\boldsymbol{x}) \]
ここで、\(\boldsymbol{J} = (\frac{\partial f_i}{\partial x_j})\) はヤコビ行列を表します。
最急降下方向
最急降下方向は、次の式で与えられます。
\[ \boldsymbol{\delta_{\mathrm{sd}}} = -\boldsymbol{J}^{\top} \boldsymbol{f}(\boldsymbol{x}) \]
目的関数を最急降下方向に沿って線形化すると、次のようになります。
\[ \begin{aligned} F(\boldsymbol{x} + t\boldsymbol{\delta_{\mathrm{sd}}}) &\approx \frac{1}{2} \|\boldsymbol{f}(\boldsymbol{x}) + t\boldsymbol{J}(\boldsymbol{x})\boldsymbol{\delta_{\mathrm{sd}}}\|^2 \\ &= F(\boldsymbol{x}) + t\boldsymbol{\delta_{\mathrm{sd}}}^{\top} \boldsymbol{J}^{\top} \boldsymbol{f}(\boldsymbol{x}) + \frac{1}{2} t^2 \|\boldsymbol{J}\boldsymbol{\delta_{\mathrm{sd}}}\|^2 \end{aligned} \]
コーシー点の計算
コーシー点におけるパラメータ \(t\) の値は、上記の式を \(t\) で微分してゼロとすることで得られます。その結果、 \(t\) は次のようになります。
\[ t = -\frac{\boldsymbol{\delta_{\mathrm{sd}}}^{\top} \boldsymbol{J}^{\top} \boldsymbol{f}(\boldsymbol{x})}{\|\boldsymbol{J}\boldsymbol{\delta_{\mathrm{sd}}}\|^2} = \frac{\|\boldsymbol{\delta_{\mathrm{sd}}}\|^2}{\|\boldsymbol{J}\boldsymbol{\delta_{\mathrm{sd}}}\|^2} \]
ステップの選択
与えられた信頼半径 \(\Delta\) のもとで、パウエルのドッグレッグ法では、更新ステップ \(\delta_k\) を以下のように選択します。
1. ガウス・ニュートンステップ \(\boldsymbol{\delta_{\mathrm{gn}}}\) が信頼領域内にある場合（\(\|\boldsymbol{\delta_{\mathrm{gn}}}\| \le \Delta\) の場合）、ステップは \(\boldsymbol{\delta_{\mathrm{gn}}}\) となります。
2. ガウス・ニュートンステップと最急降下ステップの両方が信頼領域外にある場合（\(\|t\boldsymbol{\delta_{sd}}\| > \Delta\) の場合）、ステップは \( \frac{\Delta}{\|\boldsymbol{\delta_{\mathrm{sd}}}\|}\boldsymbol{\delta_{\mathrm{sd}}}\) となります。
3. ガウス・ニュートンステップが信頼領域の外にあり、かつ最急降下ステップが内側にある場合、ステップは、以下の式を満たす \(s\) を求めたものになります。
\[ t\boldsymbol{\delta_{\mathrm{sd}}} + s(\boldsymbol{\delta_{\mathrm{gn}}} - t\boldsymbol{\delta_{\mathrm{sd}}}) \]
このステップは、信頼領域の境界を満たすように計算されたドッグレッグステップとなります。
まとめ
ドッグレッグ法は、ガウス・ニュートン法と最急降下法を効率的に組み合わせ、信頼領域の概念を導入することで、非線形最小二乗問題に対する安定した解法を提供します。その反復プロセスは、ゴルフのドッグレッグホールのように、ガウス・ニュートンステップと最急降下ステップを組み合わせて進行し、最適解へと収束していきます。
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。