WOLFRAM言語チュートリアル

制約付き最適化関数の比較

NMinimizeNMaximizeMinimizeMaximizeは,大域的最適化アルゴリズムを使用するので,大域的最適値が必要なときに適している.

MinimizeMaximizeは,任意の多項式問題を含む最適化問題のクラスでの厳密な大域的最適値を見付けることができる.しかし,使用されるアルゴリズムには膨大な漸近的計算量があるため,変数の数が少ない問題にしか適さない.

Maximizeは数値的に不安定な場合にでも,常に大域的最大値を見付ける.ここで,左辺の制約条件はである.
In[1]:=
Click for copyable input
Out[1]=
この入力は上の入力と21番目の桁の数だけが異なっているが,解は大きく異なっており,特に最大点の場所の差が顕著である.アルゴリズムについては,16桁精度を使うとどちらの問題も同じに見えるので,どちらも正確に解くことができない.
In[2]:=
Click for copyable input
Out[2]=
NMaximizeはデフォルトで機械精度数を使うが,どちらの問題を解くこともできない.
In[3]:=
Click for copyable input
Out[3]=
In[4]:=
Click for copyable input
Out[4]=

FindMinimumは局所的最小点を見付けようとするので,局所的最適値が必要な場合や,問題には1つの最適値しかない,または異なる初期値を使って見付けられる最適値が数個しかないということが予め分かっている場合に適している.

局所的最適化のときでも,小さい問題にはNMinimizeを使った方がよい.NMinimizeは4つの直接探索法(NelderMead法,微分進化法,焼きなまし法,ランダムサーチ法)の中の1つを使い,KKT条件の解,内点法,ペナルティ法を組み合せて使うことで解を微調整する.したがって,効率が問題にならない場合は,NMinimizeの方が大域的最適化処理になるだけでなくFindMinimumよりもロバストである.

次は,4つの変数を持つ問題におけるNMinimizeのデフォルトの動作である.

In[5]:=
Click for copyable input
Out[9]=

下は,KKTとFindMinimumの2つのポストプロセッサがデフォルトの結果を出さないことを示している.FindMinimumという名前は,のオプション値として使われると,制約条件付き最適化問題を制約条件のない最適化問題に変換し,(制約条件のない)FindMinimumを使って解くのにペナルティ法が使われる過程を表している.

In[10]:=
Click for copyable input
Out[10]=
In[11]:=
Click for copyable input
Out[11]=

しかし,効率が重要ならば,極小値だけが必要なとき,よい初期値を与えることができるとき,問題の最小値は1つしかない(凸状等)ことが分かっているとき,問題が大きい/高価なときにFindMinimumを使うとよい.以下ではFindMinimumNMinimizeを使って7つの変数を持つ同じ問題を解く.制約条件は比較的高価である.この場合は,明らかにFindMinimumの方がNMinimizeよりも格段に速い.

In[12]:=
Click for copyable input
In[14]:=
Click for copyable input
Out[14]=
In[15]:=
Click for copyable input
Out[15]=