大域的非線形数値最適化

はじめに

制約条件付きの非線形最適化に対する数値アルゴリズムは,大まかに分けると勾配法と直接探索法とに分けられる.勾配法では,第1導関数(勾配)か第2導関数(ヘッシアン)が使われる.この例には逐次二次計画(SQP)法,拡大ラグランジュ法,非線形内点法がある.直接探索法では,導関数情報は使われない.この例としては,Nelder-Mead法,遺伝的アルゴリズム,微分進化法,焼きなまし法がある.直接探索法の方が収束が遅い傾向があるが,関数と制約条件のノイズの存在への耐性は強い.

通常,アルゴリズムは問題の局所的なモデルを構築するだけである.また,そのようなアルゴリズムの多くは目的関数の減少,目的関数と制約条件の組み合わせであるメリット関数の減少を要求し,反復プロセスの収束を確実にする.収束した場合,このアルゴリズムは局所的最適値だけを見付けるため,「局所的最適化アルゴリズム」と呼ばれる.Wolfram言語では,局所的最適化問題はFindMinimumを使って解くことができる.

一方,大域的最適化アルゴリズムは,一般に目的・メリット関数の増加と減少を許可することにより,大域的最適値を見付けようとする.このアルゴリズムは通常計算的により高価である.大域的最適値問題は,Minimizeを使って厳密に解くことも,NMinimizeを使って数値的に解くこともできる.

下の非線形計画問題

Minimizeで解く.厳密解が得られる.

In[1]:=
Click for copyable input
Out[1]=
次に,同じ問題を数値的に解く.NMinimizeは機械数の解を返す.
In[2]:=
Click for copyable input
Out[2]=
FindMinimumは数値的に局所的最小値を見付ける.この例では,見付かった局所的最小値は,大域的最小値でもある.
In[3]:=
Click for copyable input
Out[3]=

NMinimize関数

NMinimizeNMaximizeは制約条件付きの大域的最適地を見付けるためのいくつかのアルゴリズムを実装する.これらのメソッドは非常に柔軟であるため,微分不可能であったり連続ではない関数,および局所的最適値では簡単にとらえられない関数を扱うことができる.

大域的最適値を見付けることは,制約条件がなかったとしてもかなり難しくなることもあるので,使用されるメソッドは失敗する可能性もある.関数を異なる初期条件で数回最適化して最高の結果を取るとよいことがよくある.

の最大値を見付ける.
In[46]:=
Click for copyable input
Out[46]=
制約条件 および のもとで の最小値を見付ける.
In[47]:=
Click for copyable input
Out[47]=

NMinimizeNMaximizeの制約条件は,リストか方程式・不等式・領域指定の論理結合のどちらかである.方程式と不等式は非線形でもよい.強い方程式は近似数値の操作に限界があるため,弱い方程式に変換される.Elementを使って,Element[x,Integers]あるいはxIntegersのように変数の領域を指定する.変数は整数か実数であり,指定されていない限りは実数であると想定される.点が実行可能領域を出たときは,一般にペナルティを加えることにより制約条件が強制される.

制約条件にはAndOr等の論理演算子を入れることができる.
In[3]:=
Click for copyable input
Out[3]=
ここで は整数になるよう制約される.
In[4]:=
Click for copyable input
Out[4]=

NMinimizeが動くようにするためには,開始地点となる矩形の初期領域が必要である.これは初期値に他の数値メソッドを与えることと同じである.初期領域はそれぞれの変数に有限の上限と下限を与えることにより指定する.これは制約条件に を入れるか変数にを入れることで指定できる.この両方を与えると,変数の限界が初期領域として使用され,制約条件は制約条件としてのみ使われる.変数 x に対して初期領域が指定されていない場合は,デフォルトの初期領域が使われる.異なる変数は異なる方法で定義される初期領域を持つことができる.

ここでは初期領域が変数から取られている.問題は制約条件を持たない.
In[5]:=
Click for copyable input
Out[5]=
ここでは初期領域が制約条件から取られている.
In[6]:=
Click for copyable input
Out[6]=
以下では の初期領域は制約条件から, の初期領域は変数から, の初期領域はデフォルトから取られている.問題は では制約条件がないが では制約条件がある.
In[7]:=
Click for copyable input
Out[7]=
多項式で最小値を持つ.が極小値のひとつを見付ける.
In[48]:=
Click for copyable input
Out[48]=
異なるを使うと別の極小値を見付けることができる.
In[50]:=
Click for copyable input
Out[50]=

NMinimizeNMaximizeには使用できる最適化メソッドがいくつかある.そのメソッドとはAutomaticである.最適化メソッドはMethodオプションで制御できる.このオプションはメソッドを文字列として取るか,最初の要素が文字列としてのメソッドであり残りの要素がメソッド特定のオプションとなっているリストを取る.左辺のメソッド特定のオプションはすべて文字列として与えなければならない.

以下の関数には多数の極小値がある.
In[51]:=
Click for copyable input
Out[53]=
を使って極小値を見付ける.
In[54]:=
Click for copyable input
Out[54]=
複数の初期値を持つを使って最小値を見付ける.
In[55]:=
Click for copyable input
Out[55]=

デフォルトメソッドを使うと,NMinimizeは問題のタイプにより使用するメソッドを選ぶ.目的関数と制約条件が線形ならば,LinearProgrammingが使われる.整数変数がある場合,または目的関数の頭部が数値関数でない場合は,微分展開が使われる.これ以外の場合は,Nelder-Meadが使われるが,これではうまくいかない場合は微分展開に切り替えられる.

NMinimizeで使用されるメソッドは反復毎に向上しないかもしれないので,収束は数回の反復後ごとにチェックされる.

制約条件付きの大域的最適化の数値アルゴリズム

NelderMead法

NelderMead法は直接探索法である. 個の変数の関数の場合,このアルゴリズムは 次元空間にポリトープの頂点を形成する 個の点の集合を維持する.Nelder-Mead法はシンプレックス法と呼ばれることもよくある.しかし,これは線形計画法で使用する有名なシンプレックス法とは異なる.

各反復において,個の点 はポリトープを形成する.点は となるように並ぶ.次に最悪の点 に代り,新しい点が生成される

を,最善の 個の点で構成されるポリトープの重心 とする.試行点 は重心を通過する最悪の点を反映することにより生成され,となる.ここで がパラメータである.

新しい点 が新しい最悪の点でも最善の点でもないならば,であり,に代る.

新しい点 が最善の点よりもよい場合はであり,反映は非常に成功するため,反映を にまで拡張して実行することができる.ここで はポリトープを拡大するためのパラメータである.拡大が成功すると であり, に代る.それ以外の場合は,失敗した拡大と に代る.

新しい点 が2番目に最悪の点よりも悪い場合は で,ポリトープは大きすぎるため縮小する必要がある.新しい試行点は次のように定義される.

ここでがパラメータである.ならば,縮小は成功で,に代る.それ以外の場合はさらに縮小が実行される.

新しいポリトープと古いポリトープの最適関数値の間の差分と,新しい最善点と古い最善点の間の距離が,AccuracyGoalおよびPrecisionGoalにより与えられる許容誤差よりも小さい場合に,この過程は収束したものとみなされる.

厳密に言うと,NelderMead法は本当の大域的最適化アルゴリズムではないが,実際には多くの極小値を持たない問題でうまく動作する.

オプション名
デフォルト値
"ContractRatio"0.5縮小に使われる割合
"ExpandRatio"2.0展開に使われる割合
"InitialPoints"Automatic初期値の集合
"PenaltyFunction"Automatic不当な点にペナルティを与えるために制約条件に適用する関数
"PostProcess"Automatic局所的な検索メソッドを使って事後処理を行うかどうか
"RandomSeed"0乱数生成に使う初期値
"ReflectRatio"1.0反射に使う割合
"ShrinkRatio"0.5縮小に使われる割合
"Tolerance"0.001制約条件違反を受け入れるための許容値

に特定のオプション

以下ではを使って単位円板内の関数を最小化する.
In[82]:=
Click for copyable input
Out[82]=
これはすべて異なる深さのいくつかの極小値を持つ関数である.
In[83]:=
Click for copyable input
Out[83]=
デフォルトパラメータでははあまりに簡単に極小値に捕らえられる.
より攻撃的でシンプレックスを小さくする可能性の少ない設定を使うと,前よりよい結果が得られる.

微分進化法

微分進化法は,確率関数の簡単な最小解である.

このアルゴリズムは 個の点を持つ母集団を維持する.ここで通常 であり, は変数の数である.

アルゴリズムの各反復の間に, 個の点を持つ新しい母集団が生成される. 番目の新しい点は古い母集団の中から3つの無作為な点 を抽出し,を形成することで生成される.ここで は実数のスケール因子である.次に から確率 番目の座標を取るか,そうでない場合は から座標を取ることにより および から新しい点 が構築される. ならば,母集団の で置き換えられる.確率 オプションで制御する.

最適な関数の値の間の差分,および新しい母集団と古い母集団における関数の最適点の差分が,AccuracyGoalおよびPrecisionGoalにより与えられる許容誤差より小さいならば,プロセスは収束したものとみなされる.

微分進化法は,計算的には高価であるが,比較的ロバストであり局所的最小値の多い問題にうまく作用する.

オプション名
デフォルト値
"CrossProbability"0.5遺伝子がから取られる確率
"InitialPoints"Automatic初期値集合
"PenaltyFunction"Automatic不当な点にペナルティを与えるために制約条件に適用する関数
"PostProcess"Automatic局所的な検索メソッドを使って事後処理を行うかどうか
"RandomSeed"0乱数生成に使う初期値
"ScalingFactor"0.6つがいの相手を生成する差分ベクトルに適用するスケール
"SearchPoints"Automatic展開に使われる母集団の大きさ
"Tolerance"0.001制約条件違反を受け入れるための許容値

に特定のオプション

以下ではを使って単位円板内の関数を最小化する.
In[125]:=
Click for copyable input
Out[125]=
以下の制約条件付き最適化問題には最小値がある.
In[126]:=
Click for copyable input
In[127]:=
Click for copyable input
のデフォルト設定では,満足いく結果が得られない.
In[130]:=
Click for copyable input
Out[130]=
を調整すると,ずっとよい結果が得られる.この場合,増加したによりは整数変数についての移動性が向上する.
In[131]:=
Click for copyable input
Out[131]=

焼きなまし法

焼きなまし法は,確率関数の簡単な最小解である.これは焼きなましの物理的プロセスからできたもので,金属物体が高温に熱され,ゆっくりと冷却されるようにしたものである.このプロセスにより,金属の原子構造は低エネルギー状態に落ち着くので,金属は丈夫になる.最適化では,焼きなましにより,構造が局所的最小値から逃れ,よりよい大域的最小値を探し,そこに落ち着くようにできる.

各反復において,現行点 の近傍に新しい点 が生成される.近傍の半径は各反復のたびに小さくなる.これまでに見付かった最適点 の記録も取られる.

ならば で置き換えられる.それ以外の場合は,確率 に置き換えられる.ここで により定義された関数, は現在の反復, は目的関数値の変更, は前の反復からの目的関数の値である. のデフォルト関数はである.

メソッドと同様に,も複数の初期値を使い,そのそれぞれから最適値を見付ける.

オプションにより与えられるデフォルトでの初期値の数はであり,ここで は変数の数である.

これはそれぞれの初期値について,反復の最大値に達する,メソッドが1点に収束する,あるいはにより与えられた反復回数の間ずっと1点に留まるかするまで繰り返される.

オプション名
デフォルト値" "
"BoltzmannExponent"Automatic確率関数の指数
"InitialPoints"Automatic初期値集合
"LevelIterations"50指定された点に留まってもよいとする最大反復回数
"PenaltyFunction"Automatic不当な点にペナルティを与えるために制約条件に適用する関数
"PerturbationScale"1.0乱数ジャンプに対するスケール
"PostProcess"Automatic局所的な検索メソッドを使って事後処理を行うかどうか
"RandomSeed"0乱数生成に使う初期値
"SearchPoints"Automatic展開に使われる母集団の大きさ
"Tolerance"0.001制約条件違反を受け入れるための許容値

に特定のオプション

を使って2つの変数の関数を最小化する.
In[62]:=
Click for copyable input
Out[62]=
多数の極小値を持つ関数.
In[63]:=
Click for copyable input
Out[65]=
の刻み幅は,デフォルトで極小値から逃れられるほど大きくない.
In[68]:=
Click for copyable input
Out[68]=
を大きくすると,刻み幅が大きくなり結果もよくなる.
In[69]:=
Click for copyable input
Out[69]=
以下ではが指数関数的な冷却関数を使うよう指定されており,これで収束が格段に速くなる(修正も同様に使われている).
In[70]:=
Click for copyable input
Out[70]=

ランダムサーチ

ランダムサーチ法はランダムな初期点の母集団を形成することにより動作し,各初期点から局所的な最適化メソッドを使い,局所的最小値へ収束する.最適な局所的最小値が解に選ばれる.

使用できる局所的検索メソッドはAutomaticである.デフォルトメソッドはAutomaticである.これは制約条件に対してペナルティ条項が加わったシステムに適用される制約条件のないメソッドでFindMinimumを使う.Methodの場合,非線形内点法が使われる.

オプションで与えられる初期値のデフォルトでの数は,であり,ここで は変数の数である.

の収束は各初期値に対する局所的メソッドの収束により決定する.

は高速であるが,各検索空間の次元であまりうまくスケールされない.またFindMinimumと同じ限界もある.これは,離散問題および導関数や割線法では問題に対する便利な情報が得られないような問題には向かない.

オプション名
デフォルト値
"InitialPoints"Automatic初期値集合
"Method"Automatic最小化に使用するメソッド
"PenaltyFunction"Automatic不当な点にペナルティを与えるために制約条件に適用する関数
"PostProcess"Automatic局所的な検索メソッドを使って事後処理を行うかどうか
"RandomSeed"0乱数生成に使う初期値
"SearchPoints"Automatic展開に使われる母集団の大きさ
"Tolerance"0.001制約条件違反を受け入れるための許容値

特定のオプション

を使い,単位円板内部の関数を最小化する.
In[71]:=
Click for copyable input
Out[71]=
以下は,深さがすべて異なり,一般に最適化が難しい極小値を持つ関数である.
In[72]:=
Click for copyable input
Out[72]=
のデフォルトの数では,最小値が見付けられないことがある.
を大きくすると,よい解が得られる.
初期値として使用する点を格子上に生成する.
In[75]:=
Click for copyable input
Out[75]=
次では非線形内点法を使い,平方和の最小値を見付ける.
In[76]:=
Click for copyable input
Out[80]=
問題のクラスによっては,解の質に影響を与えることなくの数を制限がずっと速くできる.
In[81]:=
Click for copyable input
Out[81]=