ネルダー–ミード法

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

概要[編集]

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

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

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

擬似コード[編集]

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

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