はじめに

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

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

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

下の非線形計画問題をMinimizeで解く．

厳密解が得られる．

NMinimize関数

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

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

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

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

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

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

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

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

Nelder–Mead法

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

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

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

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

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

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

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

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

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

NelderMeadに特定のオプション

微分進化法

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

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

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

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

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

DifferentialEvolutionに特定のオプション

焼きなまし法

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

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

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

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

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

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

SimulatedAnnealingに特定のオプション

ランダムサーチ

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

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

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

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

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

RandomSearch特定のオプション

関連するテクニカルノート

▪
• 制約条件付き最適化
▪
• 線形最適化
▪
• 局所的非線形数値最適化
▪
• 厳密な大域的最適化