制約無し非線形最適化手法のいろいろ
非線形最適化の教科書を読むと、最急降下法、ニュートン法、共役勾配法、準ニュートン法・・・、などなど本当に様々な手法がでてきます。また、Ceres-Solverのような最適化ライブラリでも様々なオプションを選択可能になっており、どれを選んだらいいのかよく分かりません。そこで、ざっと主要な非線形最適化方法を分類してみて、それを手法選択の指針にするというのが、この記事の目的です。
まず、最初に今回説明する各種手法を並べます。
大まかに言うと、単純だが安定性は高い最急降下法と、収束は速いが安定性が低く収束しないこともあるニュートン法の戦いだと思っていいと思います。ニュートン法は、性能はよいがイタレーション毎の処理が重いため、処理を減らすための様々な改善がなされたアルゴリズム（図中のニュートンファミリー）が提案されています。また、これら2つのグループのいいとこどりをしようという、信頼領域法というやり方も考案されており、どちらかというとこの中間のやり方が主流になっています（Ceres-Solverのデフォルトもレーベンバーグ・マーカート法）。なお、この信頼領域法は、中で最急降下法とニュートンファミリーのどれかを組合わせる形になっているので、純粋に新しい手法というよりは、うまく2つを組合わせるような上位レベルの組合せ手法となっています。
では、個々の手法の中身を見る前に、今回扱う制約無し非線形最適化について明らかにしておきます。ここでは、以下の式を満たすようなx*を求めることを非線形最適化と呼びます。xはn次元ベクトルです。また、最小化する関数fを目的関数と呼びます。
$$x^*=\underset{x}{\arg\min}f(x) \tag{1}$$また、最小二乗法という問題設定もあります。本来、理論値であればゼロになるはずのモデル（式群）があった時に、ノイズが混ざった観測値を用いて計算した式の二乗を最小化することでモデルのパラメータを推定する手法です。最小二乗法は、以下の数式で一般化されます。これは非線形最適化のサブセットになります。Fはm次元のベクトル（m個の関数、またはm次元ベクトルを出力する関数）で、xはn次元ベクトルです。
$$x^*=\underset{x}{\arg\min}\|F(x)\|^2 \tag{2}$$最小二乗問題に対しても各非線形最適化ツールをそのまま適用することができますが、逆に表中のガウスニュートン法のように最小二乗法に特化したツールもあります。
さて、非線形最適化の基本的な考え方は、「目的関数の勾配の”だいたい”逆側に進んでいけばいつか最小値にたどり着ける”だろう”」というもので、イタレーションを伴う反復手法になっています。この”だいたい”とか”だろう”がポイントで、実際、最急降下法は勾配のきっかり逆側に進んでいく手法で最小値にたどり着けることが保証されていますが収束は遅くなります、一方、ニュートン法は勾配の逆側とは少し違う方向に進むことで速く収束しますが、逆に結果たどり着けないこともあります。
最急降下法
まず、最も単純だがその分安定しているという最急降下法の説明からしていきます。ある反復での、ベクトルの位置がxだとして以下のように目的関数をテイラー展開の1次までの項で近似します。
$$f(x+\Delta x)\approx f(x)+\nabla f(x)\Delta x \tag{3}$$そうすると、勾配の逆方向に進めば目的関数の値が、必ず現在のf(x)から小さくなることになります。しかし、実際には目的関数を1次近似しているにすぎないので、その方向に進んでもいつか極小値に行き当たり、また増加に転じます。そこで、その方向にある程度進んだら再び勾配方向を求めてその反対方向に進むということを繰り返すのが最急降下法です。
直線探索
さて、では1反復中に勾配方向にどれぐらい（これを探索ステップといいます）進めばよいのでしょうか？極小値まで行ければよいのですが、まじめに極小値を探すのはけっこう大変です。一般的には、アルミホ（Armijo）条件もしくはウルフ（Wolfe）条件という、より満たすのが簡単な条件を満たすようなステップをざっくり求めて、（まだ極小値に至っていないとしても）次の反復に進むという方法がとられます。
ニュートン法
最急降下法はとにかく収束が遅いというのが欠点です。一方、ニュートン法は非常に収束が速いというのが利点な一方、必ず収束するとは限らないという性質があります。ニュートン法では、目的関数をテイラー展開の2次の項まで使って近似します。
$$f(x+\Delta x)\approx f(x)+\nabla f(x)\Delta x+\Delta x^T\nabla^2 f(x)\Delta x \tag{4}$$これは、Δxの2次式とみなせるので、Δxで微分してゼロになるところが極値になります。つまり、以下の等式を満たすようなΔxをステップとして選べばよいのです。ここで、Hはヘッセ行列（\(=\nabla^2_x f\)）を表します。
$$H\Delta x=-\nabla f \tag{5}$$ニュートンファミリー
ニュートン法は優れた方法なのですが、主に以下の2点の問題があります。
- ヘッセ行列の逆行列計算が大変
- ヘッセ行列自体の計算が大変
そこで、いくつかのニュートン法の亜種が考えられました。まず、1を解決するために考えられたのが、共役勾配法です。また、2を解決するために考えられたのが、ガウスニュートン法と準ニュートン法です。準ニュートン法には、さらにメモリ消費量を抑える記憶制限準ニュートン法というやり方もあります。
共役勾配法
式(5)を解かなくてもΔxの方向さえ分かれば、その方向（共役勾配）に直線探索して極値を探しに行けばいい。これが共役勾配法の基本的な考え方です。例えば2次元空間で考えると、目的関数の等高線の接線方向 t と勾配方向は直交するので、それらの内積はゼロになります。ニュートン法では式(5)よりヘッセ行列とΔxの積が勾配方向と同じ向きになるので、以下の式が成り立ちます。
$$t^TH\Delta x = 0 \tag{6}$$共役勾配 m は、接線 t と勾配が作る面上にあるはずなので以下のように表せます。
$$m=\nabla f+\alpha t \tag{7}$$この関係性を用いて、接線方向 t と勾配とヘッセ行列からαを導き出すことができます。さて、ここで前のイタレーションでの探索結果として得られる極小地点では、探索方向と目的関数の勾配が直行しているはずです。つまり、前のイタレーションでの探索方向が、そのまま次のイタレーションでの接線方向 t になっているということになります。なので、前のイタレーションでの共役勾配を用いて再帰的に次のイタレーションでの共役勾配が求められるのです。
αの計算にはヘッセ行列を使うため、それでもまだ大変さが残ります。そのため、ビール・ソレンソンの式、ポラック・リビエールの式、フレッチャー・リーブスの式といった近似的な計算手法も考え出されています。なお、3次元以上の空間では接線が接面になり超接面になっていくため、厳密には上記の議論は成り立ちませんが、同様の方法で効果が得られることが知られています。
ガウスニュートン法
問題が式(2)のような最小二乗問題の場合、ヘッセ行列の計算を簡略化する方法があります。式(2)をxで偏微分すると以下を得ます（ただし、\(\nabla{F}\)はヤコビ行列 J を表す）。
$$\nabla{f}=F^T\nabla{F} \tag{8}$$また、二次微分は以下のとおり計算されます（ただし、\(F^T\nabla^2{F}\)はFの各要素のヘッセ行列にFの各要素をそれぞれ掛けて足し合わせたもの）。
$$\nabla^2{f}=F^T\nabla^2{F}+\nabla{F}^T\nabla{F} \tag{9}$$さて、ここで x が十分最適値に近い場合、最小二乗問題の問題設定より関数値がゼロに近づくはずです。つまりFの項が消えて二次微分は以下のように近似されます。
$$\nabla^2{f}=H\approx\nabla{F}^T\nabla{F}=J^T J \tag{10}$$つまり、2次微分を計算してヘッセ行列を得る代わりに、一次微分であるヤコビ行列の掛け算で済ますことが可能になるのです。これがガウスニュートン法です。
準ニュートン法
準ニュートン法は、また別のやり方でヘッセ行列を近似しようというものです。まず、勾配ベクトルのテイラー展開を考えます。
$$\nabla f(x+\Delta x)\approx\nabla f(x) + \nabla^2 f(x)\Delta x \tag{11}$$ここで、x がある反復でのベクトル値でΔxが移動量だとすれば、以下の関係性が得られます。これをセカント条件といいます。
$$\nabla f(x_{k+1})-\nabla f(x_{k})=H(x_{k+1}-x_{k}) \tag{12}$$準ニュートン法では、このセカント条件を満たすという意味において、ヘッセ行列と似たような正定値行列をヘッセい行列の代わりに使うことで計算を簡略化します。ただし、そのような近似行列を直接的に探索するのではなく、前の反復における近似行列を用いて次の反復での近似行列を求めるための方法として、DFP（Davidon, Fletcher-Powell）公式、BFGS（Broyden, Fletcher, Goldfarb, Shanno）公式などが提案されています。また、ヘッセ行列だけでなく、ヘッセ行列の逆行列の再帰的な更新式も同様に提案されており、逆行列の計算も省くことが可能になっています（ただし、必ずしもこちらが軽くなるとは限らない）。通常、準ニュートン法はアルミホ条件やウルフ条件を用いた直線探索と組み合わせて用いられます。
記憶制限準ニュートン法
準ニュートン法では、前の反復の近似行列を全て記憶しておく必要があり、大規模な問題では記憶容量が問題になることがあります。そこでヘッセ行列を再帰的なベクトルの組合せで表しておき、そのベクトルの一部のみを用いることで、記憶容量を減らす方法が記憶制限準ニュートン法です。なお、記憶制限BFGS法で保持するベクトルが1本だけの時、共役勾配法と同じ探索ベクトルが得られることが知られており、その意味では記憶制限準ニュートン法は準ニュートン法と共役勾配法の中間的な手法と解釈できます。
信頼領域法
ニュートン法（ファミリー）の利点は収束が速いことですが、最大の弱点は二次近似が効かない時にあらぬ方向に行ってしまうことがあり、結果収束しない可能性があることです。そこで、反復毎に二次近似の信頼度を判断する範囲（信頼領域）を定めておき、その範囲で二次近似が信頼できそうならニュートン法を用い、そうでなければ最急降下法を用いる、また信頼度に応じて信頼領域を拡げたり縮めたりする、というようなやり方を総称して信頼領域法といいます。よく知られた信頼領域法として、レーベンバーグ・マーカート法とドッグレッグ法があります。
レーベンバーグ・マーカート法
レーベンバーグ・マーカート法の基本的な考え方は、式(5)を使う代わりに以下の式を使うというものです。Iは単位行列です。
$$(H+\lambda I)\Delta x=-\nabla f \tag{13}$$これは、λが小さい時はニュートン法と同様になりますが、逆にλが十分大きくなると探索方向が勾配方向の逆方向に近くなるので最急降下法に近くなると言えます。つまり、λの大小を二次近似の信頼度と紐づけることにより最適な探索方向を見つけるのです。
最初にレーベンバーグが提案したのはこの式ですが、フレッチャーは単位行列 I を使う代わりにヘッセ行列の対角成分からなる行列を使うほうが効率的だと提案しており、またその亜種も存在します。今日では単位行列がそのまま使われることは少ないようです。
ドッグレッグ法
ドッグレッグ法もレーベンバーグ・マーカート法と同様、最急降下法の探索方向とニュートン法の探索方向を重みづけしてその中間をとる方法です。ドッグレッグ法では、最急降下方向に移動した時の二次近似モデルの最小点をコーシー点と呼び、そのコーシー点（ベクトル）とニュートン法から得られる更新ベクトルと信頼領域の半径から探索方向を決定します。コーシーベクトルとニュートンベクトルをつなげた形が犬の足に似ているところからドッグレッグと呼ばれています。
以上、各アルゴリズムの詳細については以下の参照文献を参照ください。
参照
- 「これなら分かる最適化数学 基礎原理から計算手法まで」金谷健一
- ISBN978-4-320-01786-3
- 非常に分かりやすい、厳密性よりも分かりやすさ優先
- 最急降下法、ニュートン法、共役勾配法、ガウスニュートン法、レーベンバーグ・マーカート法
- 「工学基礎 最適化とその応用」 矢部博
- ISBN4-901683-34-9
- 金谷よりも厳密性と網羅性を重視している分、わかりづらいがゆっくり読めば分かる
- 最急降下法、ニュートン法、共役勾配法、準ニュートン法、記憶制限準ニュートン法、ドッグレッグ法
- Ceres-Solver: Solving Non-Linear Least Squares
- 最小二乗目線で書かれているが、Ceres-Solverで使われている最適化手法を網羅的に紹介している。比較的分かりやすい
- 最急降下法、ニュートン法、共役勾配法、準ニュートン法、記憶制限準ニュートン法、レーベンバーグ・マーカート法、ドッグレッグ法
- Wikipedia: Levenberg–Marquardt algorithm
- レーベンバーグ・マーカート法について詳しく書いている文献が無かったため参照