ネルダー–ミード法

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

概要

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

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

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

擬似コード

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

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