ネルダー–ミード法

ネルダー–ミード法（ネルダー–ミードほう、テンプレート:Lang-en-short）や滑降シンプレックス法（テンプレート:Lang-en-short）やアメーバ法（テンプレート:Lang-en-short）は、最適化問題のアルゴリズム。導関数は不要。1965年に John A. Nelder と Roger Mead が発表した^[1]。

概要

n + 1 個の頂点からなる n 次元の単体（シンプレックス）をアメーバのように動かしながら関数の最小値を探索する。反射、膨張、収縮の3種類を使い分けながら探索する。

Rの汎用的最適化の optim() のデフォルトのアルゴリズムとしても使われている。

線形計画法の1つであるシンプレックス法と名前はまぎらわしいが、基本的に無関係である。

擬似コード

$f (𝐱)$ の最小化を行う。 $𝐱$ は n 次元のベクトル。関数の引数は探索開始点。定数は一般的には $α = 1, γ = 2, ρ = 1 / 2, σ = 1 / 2$ を使用する。 $𝐞_{i}$ は単位ベクトル。

function nelderMead( $𝐱_{1}$ ) {
     $𝐱_{i + 1} = 𝐱_{1} + λ 𝐞_{i} for all i \in {1, \dots, n}$ 
    while (所定のループ回数 や 値の改善が小さくなった) {
         $f (𝐱_{1}) \leq f (𝐱_{2}) \leq \dots \leq f (𝐱_{n + 1})$  となるようにソートする。
    
        // 重心（ $𝐱_{n + 1}$ は除外）
         $𝐱_{0} = \frac{1}{n} \sum_{i = 1}^{n} 𝐱_{i}$  
    
         $𝐱_{r} = 𝐱_{o} + α (𝐱_{o} - 𝐱_{n + 1})$ 
        if  $(f (𝐱_{1}) \leq f (𝐱_{r}) < f (𝐱_{n}))$  {
            // 反射
             $𝐱_{n + 1} = 𝐱_{r}$ 
        } else if  $(f (𝐱_{r}) < f (𝐱_{1}))$  {
            // 膨張
             $𝐱_{e} = 𝐱_{o} + γ (𝐱_{r} - 𝐱_{o})$ 
            if  $(f (𝐱_{e}) < f (𝐱_{r}))$  {
                 $𝐱_{n + 1} = 𝐱_{e}$ 
            } else {
                 $𝐱_{n + 1} = 𝐱_{r}$ 
            }
        } else {
            // 収縮
             $𝐱_{c} = 𝐱_{o} + ρ (𝐱_{n + 1} - 𝐱_{o})$ 
            if  $(f (𝐱_{c}) < f (𝐱_{n + 1}))$  {
                 $𝐱_{n + 1} = 𝐱_{c}$ 
            } else {
                 $𝐱_{i} = 𝐱_{1} + σ (𝐱_{i} - 𝐱_{1}) for all i \in {2, \dots, n + 1}$ 
            }
        }
    }
}