制約条件のない最適化

Wolfram言語には,制約条件のない最適化を行い(FindMinimumFindMaximum),非線形方程式を解き(FindRoot),非線形フィットの問題を解く(FindFit)一連のコマンドが備わっている.通常これらの関数はすべて,探索を行い,何らかの初期値から始めてオブジェクトまたはメリット関数を小さくする(FindMaximumの場合はこれを大きくする)ステップを取ることで作用する.

FindMaximumの探索プロセスは,深い霧の中で山頂を目指す登山家に例えることができる.任意の地点において登山家に分かっているのは,自分の位置,崖の傾斜,瀑布線の方向だけである.このような場合のアプローチのひとつは常に上に向かうことである.登山家が十分に険しい崖を登り続ける限り,たとえ最も高い頂上ではなくともいずれは頂に到達する.同様に,最大値の探索においては,ほとんどのメソッドが上昇法である.上昇法は,すべてのステップで高さを増し,たとえそれが最高点ではなくともある頂点に達したときに停止するメソッドである.

この登山の比喩は,極小値の探索で降下法を考えるときには逆にするとよい.ほとんどの場合,最適化に関する文献は極小値の探索の問題についての考察であり,このことがWolfram言語のコマンドの多くにも当てはまるため,ここからの記述はこの慣習に従うものとする.

例えば,以下に示す通り,関数は有界ではないので,最小値は持たない.しかし,無限数の極小値を持つ.

いくつかのユーティリティ関数を含むパッケージをロードする.
In[1]:=
Click for copyable input
次は関数x Sin[x+1]のプロットである.
In[2]:=
Click for copyable input
Out[2]=
次は関数x Sin[x+1]に対してFindMinimumが取るステップをから始めて示したものである.
In[3]:=
Click for copyable input
Out[3]=

コマンドは,このノートブックの初期化の際にロードされるOptimization`UnconstrainedProblems`パッケージの中で定義されている.このコマンドはFindMinimumを実行し,関数の経過,勾配評価,探索中に取られたステップを記録し(EvaluationMonitorオプションとStepMonitorオプションを用いる),これらを関数のプロットに重ねて表示する.ステップは青い線で,関数評価は緑の点で,勾配評価は赤の点でそれぞれ示されている.求まった極小値は大きな黒点で示されている.このプロットを見ると,FindMinimumが極小点を見付けたことが明らかである.

次は関数x Sin[x+1]についてFindMinimumから始めて取るステップを示している.
In[4]:=
Click for copyable input
Out[4]=

2から始めると,FindMinimumの探索は,最初に求まった極小値よりも関数が小さくなる別の極小値を目指している.

上記2つのプロットから,関数が下方に傾斜している点から始めると,必ずその方向の次の極小値に向うという結論に達するかもしれない.しかし,常にそうであるわけではない.一般にFindMinimumが取るステップは関数とその微分値で決まるので,微分が極めて小さければ,FindMinimumは極小点が求まるまでに極めて長い区間を行かなければならないものと想定する.

次はx Sin[x+1]についてFindMinimumから始めたステップを示している.
In[5]:=
Click for copyable input
Out[5]=

極小値に近いから始めると,最初のステップが極めて大きくなるため,FindMinimumは完全に異なる極小値を返す.

これらのコマンドはすべてその名前に"find"を含んでいる.それは,一般的に言ってこれらのコマンドが所望の条件が満足される任意の点を探す(find)ように設計されているためである.求まる点は唯一のものではないかもしれないし(根の場合),最適なものでさえないかもしれない(フィット,極小値,極大値の場合).また,上で見たように,初期条件に最も近いものでさえないかもしれない.換言すれば,目標は根,極大値,極小値ならどのような点でもよいから求めることなのである.これに対し,関数NMinimizeは関数の大域的最小値を求めようとするが,NMinimizeには通常問題の領域を限定する制約条件も与えられる.しかしながら,この一般性に対しては代価を払わなければならない.NMinimizeは,はるかに多くの仕事しなければならず,プロセスの終わりの部分で結果に磨きをかけるために関数のひとつを呼び出すことさえあるので,関数よりも一般にはるかに時間がかかるのである.

二次元ではステップの方向とステップの長さの両方を決定しなければならないため,最小化問題はより複雑になる.

以下は,関数の極小値を求めるために,FindMinimumが点から始めて取るステップを示している.
In[6]:=
Click for copyable input
Out[6]=

二次元で使用するコマンドは一次元で使用する場合と似ているが,二次元ではテップと評価を関数の等高線プロットに重ねて表示する.この例では,FindMinimumが極小値を求めるために方向を数回変更しなければならなかったことが明確である.最初のステップは最も勾配の急な降下方向(つまり,等高線に垂直,あるいは勾配に平行)であるのが分かる.最急降下法は極小値を求めるときに使用できるメソッドであるが,通常収束はそれほど速くはない.後続のステップでは,探索方向が必ずしも等高線に垂直になっていない.探索はそれまでのステップからの情報を使い,関数の曲率についての情報を集めようとする.通常これにより,進むべきよりよい方向が与えられる.最急降下法よりも収束の速い方法(より高くつく方法でもある)として,関数の二階微分を使うものがある.これは通常「ニュートン」法と呼ばれる.

次はニュートン法で取るステップである.
In[7]:=
Click for copyable input
Out[7]=

「ニュートン」法は関数の曲率について付加的な情報を持っているため,極小値に至るまでのステップ数に大きな違いが生じていることが,この例から明らかである.ニュートン法では,記号的なヘッセ行列を一旦計算した後に各ステップでこれを数値的に計算しなければならないので,最急降下法よりもステップ数は少ないが,実行時間全体で見ると長くなる可能性がある.

一般に収束率あるいは必要な総ステップ数と,ステップ毎のコストとの間にはトレードオフの関係がある.解こうとしている問題の規模により,その問題に最適なメソッドを選んだ方がよい.このドキュメントはメソッドの選択方法と,Wolfram言語の関数で最高の結果を引き出す方法を紹介するものである.ほとんどの場合で概念を示すための例題を使っており,メソッドがどのように機能するかについての理解を図るために,簡単ではあるがメソッドの背後にある数学的な理論についての説明が添えてある.

多くの場合,関数 の極小化メソッドは二次形式

に基づいている.ここで,下付き文字の 番目の反復ステップを示している.ニュートン法では二次形式は厳密なヘッセ行列 に基づいているが,他のメソッドでは一般に計算があまり高く付かないの近似を使っている.試行ステップの は一般に線形方程式の系を満足するモデルの最小化関数になるように計算される.

が十分に滑らかで が極小値に十分近ければ,ステップシーケンス で確実に極小値に収束する.しかし,通常の探索では,希望する収束が得られるほど初期値が極小値に近いことはめったにない.さらに, は実際のヘッセ行列の近似であることが多く,探索の始めでは近似が極めて不正確なことが多い.このため,ステップシーケンスに追加的な制御を加えて,収束可能性と収束率を高くする必要がある.刻み幅制御には,直線探索法および信頼領域法と呼ばれる2つのメソッドがよく使われる.

「直線探索」法では,見付かった試行ステップ それぞれに対して, となるような の方向に沿って一次元探索が行われる.この方向で を最小化するように を選ぶこともできるが,これは過剰となる.の値と勾配が減少するように要求する条件を付けると,妥当な近似 への収束が証明できる.Wolfram言語はWolfe条件と呼ばれるこれらの制約条件の式を使用している.

「信頼領域」法では,方程式(1)の二次形式 の半径 が,関数を合理的に表しているものと「信頼」される.従って,信頼領域法では制約条件のない(1)の最小値を解く代りに,制約条件 付きの(1)の最小値を求めようとする. が最小値に十分近く,モデルもよいものであれば,最小値は境界線上にあり収束も極めて速いことが多い.しかし,探索の始めのところでは,最小値は境界上にあるため,制約条件付きの問題の近似解を求めるため手法が数多くある.一旦近似解が求まれば,関数値の実際の換算値が関数値の予想換算値と比較され,実際の値が予想値にどの程度近いかによっての調整が行われる.

1変数の滑らかな関数の記号的最小化では,微分がゼロで二階微分が正になる点を求めさえすればよい.これは,複数次元では勾配が消失し,ヘッセ行列が正定値行列になることを意味する(ヘッセ行列が半正定値行列の場合は,その点が最小化関数であるが,厳密なものであるとは限らない.)数値的なアルゴリズムが収束するときは,収束の記録を取り,いつ最小値に十分近くまで迫ったかを判断しなければならない.これは取られたステップシーケンスと,これらの点における関数,その勾配,ヘッセ行列の値に基づいている.Wolfram言語の関数は通常,この判断の正しさが確定的ではない場合にメッセージを発する.しかし,不連続関数やスケールが急速に変化する関数は,いかなる代数的アルゴリズムをも惑わせることがあるので注意が必要である.

「非線形方程式」を解くときは,「極小値」を求める際と同様の問題が多く起る.事実,方程式の根でゼロになる,いわゆるメリット関数を考慮することによって,関数の最小値が0であるということが分かった上で,最小化のためのテクニックの多くを使うことができる.しかし,このアプローチを取るのが常に有利なわけではなく,非線形方程式に特化されたメソッドもある.

ここで示してある例題は,ほとんどが一次元あるいは二次元のものである.これは決してWolfram言語がそのような小規模の例題しか解けないという限界を示しているのではない.このような例題を使った方が,理論やメソッドの背後にある主原理を分かりやすく説明できるからである.