ネルダー・ミード法

ネルダー・ミード法（ダウンヒルシンプレックス法、アメーバ法、多面体法とも呼ばれる）は、多次元空間における目的関数の最小値または最大値を求める数値計算法である。これは関数比較に基づく直接探索法であり、導関数が不明な非線形最適化問題によく適用される。ただし、ネルダー・ミード法は、代替法で解決できる問題では非定常点^[1]に収束する可能性のあるヒューリスティック探索法である。 ^[2]

ネルダー・ミード法は、 1965年にジョン・ネルダーとロジャー・ミードによって提案され、^[3]スペンドリーらの方法^{[4]を発展させたものである。}

この方法では、 n次元のn  + 1 頂点の特殊な多面体である単体の概念を使用します。単体の例には、1 次元空間の線分、2 次元空間の三角形、 3 次元空間の四面体などがあります。

この方法は、目的関数が滑らかに変化し、単峰性である場合に、 n変数の問題の局所最適値を近似します。一般的な実装では関数を最小化し、を最小化することで最大化します。 ${\displaystyle f(\mathbf {x} )}$${\displaystyle -f(\mathbf {x} )}$

たとえば、吊り橋の技術者は、各支柱、ケーブル、橋脚の厚さを選択する必要があります。これらの要素は相互に依存していますが、特定の要素を変更した場合の影響を視覚化するのは簡単ではありません。このような複雑な構造のシミュレーションは、実行に非常に多くの計算コストがかかることが多く、実行ごとに数時間以上かかる可能性があります。ネルダー・ミード法では、元のバリアントでは、後述する縮小操作を除いて、反復ごとに2回以上の評価が必要ありません。これは、他の直接探索最適化方法と比較して魅力的です。ただし、提案された最適値までの全体的な反復回数は多くなる場合があります。

n次元のネルダー・ミード法は、単体として配置されたn  + 1 個のテスト ポイントのセットを維持します。次に、各テスト ポイントで測定された目的関数の挙動を外挿して新しいテスト ポイントを見つけ、古いテスト ポイントの 1 つを新しいテスト ポイントに置き換え、手法を進めます。最も単純なアプローチは、最悪のポイントを残りのnポイントの重心を通るポイントに置き換えることです。この点が現在の最良のポイントよりも優れている場合は、この線に沿って指数関数的に引き伸ばすことができます。一方、この新しいポイントが以前の値よりもあまり優れていない場合は、谷を横切っているため、単体をより良いポイントに向かって縮小します。「Numerical Recipes」からのアルゴリズムの直感的な説明: ^[5]

ダウンヒル単体法では、一連の手順を実行します。ほとんどの手順では、関数が最大になる単体の点 (「最高点」) を単体の反対側の面を通って低い点に移動します。これらの手順は反射と呼ばれ、単体の体積を保存する (したがって非退化を維持する) ように構築されます。可能であれば、この方法では単体をいずれかの方向に拡大して、より大きな手順を実行します。「谷底」に達すると、この方法は横方向に収縮し、谷を下りようとします。単体が「針の穴を通ろうとする」状況では、単体はすべての方向に収縮し、最も低い (最適な) 点の周りで引き込まれます。

現代の最適化手法とは異なり、ネルダー・ミードのヒューリスティックは、問題が現代の手法に必要な条件よりも強い条件を満たさない限り、非定常点に収束する可能性があります。^[1] ネルダー・ミードのヒューリスティックの現代的な改良は1979年から知られています。^[2]

解決する問題の実際の性質に応じて、多くのバリエーションが存在します。一般的なバリエーションでは、一定サイズの小さな単体が大まかに勾配方向 (最急降下) に従います。標高マップ上の小さな三角形が谷を下ってローカルの底に向かってひっくり返っている様子を想像してください。この方法は、フレキシブル多面体法とも呼ばれます。ただし、この方法では、あまり重要でない領域で小さくて不要なステップが実行されるため、この記事で説明する方法に比べてパフォーマンスが低下する傾向があります。

(これは、オリジナルの Nelder–Mead 論文の手順に近いものです。)

関数 を最小化しようとしています。ここで、現在のテスト ポイントは です。 ${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$${\displaystyle \mathbf {x} _{1},\ldots ,\mathbf {x} _{n+1}}$

注: 、、はそれぞれ反射、膨張、収縮、縮みの係数です。標準値は、、、です。 ${\displaystyle \alpha }$${\displaystyle \gamma }$${\displaystyle \rho }$${\displaystyle \sigma }$${\displaystyle \alpha =1}$${\displaystyle \gamma =2}$${\displaystyle \rho =1/2}$${\displaystyle \sigma =1/2}$

反射については、 は頂点の中で関連する値が最も高い頂点であるため、を除くすべての頂点によって形成される反対面の の反射でより低い値が見つかることが予想されます。 ${\displaystyle \mathbf {x} _{n+1}}$${\displaystyle \mathbf {x} _{n+1}}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle \mathbf {x} _{n+1}}$

展開では、反射点が頂点に沿った新しい最小値である場合、 からへの方向に沿って興味深い値が見つかることが期待できます。 ${\displaystyle \mathbf {x} _{r}}$${\displaystyle \mathbf {x} _{o}}$${\displaystyle \mathbf {x} _{r}}$

収縮に関しては、 の場合、すべての頂点によって形成される単体の内側に、より良い値が存在することが予想されます。 ${\displaystyle f(\mathbf {x} _{r})>f(\mathbf {x} _{n})}$${\displaystyle \mathbf {x} _{i}}$

最後に、縮小は、最大点から離れて縮小すると が増加するというまれなケースを処理します。これは、非特異最小値に十分近い場合は発生しません。その場合、より単純なランドスケープを見つけることを期待して、最低点に向かって縮小します。ただし、ナッシュは、有限精度演算では単体を実際に縮小できない場合があることを指摘し、サイズが実際に縮小されているかどうかのチェックを実装しました。^[6]${\displaystyle f}$

初期単体は重要です。実際、初期単体が小さすぎると局所探索に陥り、NM が行き詰まりやすくなります。したがって、この単体は問題の性質によって決まります。ただし、元の記事では、初期点が として与えられ、他の点が各次元に沿って固定ステップで順に生成される単体が提案されています。したがって、この方法は を構成する変数のスケーリングに敏感です。 ${\displaystyle \mathbf {x} _{1}}$${\displaystyle \mathbf {x} }$

反復サイクルを断ち切るには基準が必要です。ネルダーとミードは、現在の単体の関数値のサンプル標準偏差を使用しました。これらが許容値を下回ると、サイクルは停止し、単体の最低点が提案された最適値として返されます。非常に「平坦」な関数は、大きな領域でほぼ等しい関数値を持つ可能性があるため、ソリューションは許容値に敏感になることに注意してください。ナッシュは、収縮のテストを別の終了基準として追加しました。^[6]プログラムは終了するが、反復は収束する可能性があることに注意してください。

• アヴリエル、モルデカイ (2003)。非線形計画法: 分析と方法。ドーバー出版。ISBN 978-0-486-43227-4。
• Coope, ID; Price, CJ (2002). 「数値最適化における正の基数」.計算最適化と応用. 21 (2): 169–176. doi :10.1023/A:1013760716801. S2CID  15947440.
• ギル、フィリップ E.、マレー、ウォルター、ライト、マーガレット H. (1981)。「多変量非平滑関数の手法」。実践的最適化。ニューヨーク: アカデミック プレス。pp. 93–96。ISBN 978-0-12-283950-4。
• Kowalik, J.; Osborne, MR (1968).制約のない最適化問題に対する方法. ニューヨーク: Elsevier. pp. 24–27. ISBN 0-444-00041-0。
• Swann, WH (1972)。「直接探索法」。Murray, W. (編) 著。制約なし最適化のための数値的手法。ニューヨーク: Academic Press。pp. 13–28。ISBN 978-0-12-512250-4。

• ネルダー・ミード（ダウンヒル・シンプレックス）の説明とローゼンブロックバナナ関数による視覚化
• John Burkardt: Matlab の Nelder–Mead コード - Nelder–Mead 法のバリエーションも Matlab 関数 fminsearch によって実装されていることに注意してください。
• SciPy ライブラリの Python での Nelder-Mead 最適化。
• nelder-mead - Nelder–Mead 法の Python 実装
• NelderMead() - Go/Golang 実装
• SOVA 1.0 (フリーウェア) - さまざまなアプリケーションのためのシンプレックス最適化
• [1] - HillStormer、Nelder Meadによる非線形、多変量、線形制約付きシンプレックス最適化のための実用的なツール。