ネルダー–ミード法

ネルダー–ミード法（Nelder-Mead method）は、多次元空間における関数の最小値を探索するアルゴリズムの一つで、滑降シンプレックス法やアメーバ法とも呼ばれます。この方法は、関数の勾配（導関数）を必要としないため、微分不可能な関数や、導関数の計算が困難な場合に特に有効です。1965年にジョン・A・ネルダーとロジャー・ミードによって発表されました。

アルゴリズムの概要

ネルダー–ミード法の基本的な考え方は、n次元空間内でn+1個の頂点を持つシンプレックス（多面体）を、関数の値に応じて変形させながら移動させることで、最小値を探索することです。このシンプレックスは、あたかもアメーバのように動き回ることから、アメーバ法とも呼ばれます。具体的には、以下の3つの操作を繰り返します。

1. 反射（Reflection）: シンプレックスの中で最も関数の値が大きい頂点を、重心を軸に反対側に移動させます。
2. 膨張（Expansion）: 反射によって得られた頂点の関数の値が、元のシンプレックスの中で最も小さい値よりも小さければ、さらにその方向に拡大します。
3. 収縮（Contraction）: 反射や膨張で良い結果が得られない場合、シンプレックス全体を縮小させます。

これらの操作を繰り返すことで、シンプレックスは徐々に関数の最小値へと近づいていきます。

アルゴリズムの詳細

以下に、ネルダー–ミード法の擬似コードを示します。


function nelderMead(x1) {
// 初期シンプレックスの作成
// x1を初期点として、n個の単位ベクトルを用いて他の頂点を生成
xi+1 = x1 + λei (for all i ∈ {1, ..., n})

while (所定のループ回数や値の改善が小さくなるまで) {
// 頂点を関数値の小さい順にソート
// f(x1) <= f(x2) <= ... <= f(xn+1)

// 重心（xn+1は除く）の計算
xo = (1/n) Σ(i=1 to n) xi

// 反射点の計算
xr = xo + α(xo - xn+1)

if (f(x1) <= f(xr) < f(xn)) {
// 反射
xn+1 = xr
} else if (f(xr) < f(x1)) {
// 膨張
xe = xo + γ(xr - xo)
if (f(xe) < f(xr)) {
xn+1 = xe
} else {
xn+1 = xr
}
} else {
// 収縮
xc = xo + ρ(xn+1 - xo)
if (f(xc) < f(xn+1)) {
xn+1 = xc
} else {
// シンプレックス全体の縮小
xi = x1 + σ(xi - x1) (for all i ∈ {2, ..., n+1})
}
}
}
}


ここで、

`x1` は探索開始点となるn次元ベクトルです。
`ei` は単位ベクトルです。
`α`, `γ`, `ρ`, `σ` はそれぞれ反射、膨張、収縮の係数で、通常は `α = 1`, `γ = 2`, `ρ = 1/2`, `σ = 1/2` が用いられます。

特徴

導関数不要: 関数の導関数を必要としないため、微分不可能な関数や、導関数の計算が困難な場合にも適用できます。
実装が容易: アルゴリズムが比較的単純で、実装が容易です。
局所最適解に陥りやすい: 複雑な関数では、局所的な最適解に陥りやすく、大域的な最適解を見つけられない可能性があります。
パラメータ調整が必要: 係数 `α`, `γ`, `ρ`, `σ` の調整によって、アルゴリズムの性能が変化します。

注意点

線形計画法で用いられるシンプレックス法とは、名前が似ていますが、全く異なるアルゴリズムです。
R言語の最適化関数 `optim()` のデフォルトのアルゴリズムとして用いられています。


ネルダー–ミード法は、そのシンプルさと汎用性の高さから、様々な分野で利用されています。特に、関数の微分が難しい場合や、大域的な最適解を厳密に求める必要がない場合に、非常に便利な最適化アルゴリズムと言えるでしょう。

もう一度検索