ネルダー–ミード法

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

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

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

Summarize Timeline Top Qs Fact Check

${\displaystyle f({\textbf {x}})}$ の最小化を行う。${\displaystyle {\textbf {x}}}$ は n 次元のベクトル。関数の引数は探索開始点。定数は一般的には ${\displaystyle \alpha =1,\gamma =2,\rho =1/2,\sigma =1/2}$ を使用する。${\displaystyle {\textbf {e}}_{i}}$ は単位ベクトル。

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