ネルダー–ミード法

Nelder-Mead法から転送)

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

概要

編集

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

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

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

擬似コード

編集

  の最小化を行う。  は n 次元のベクトル。関数の引数は探索開始点。定数は一般的には   を使用する。  は単位ベクトル。

function nelderMead( ) {
     
    while (所定のループ回数 や 値の改善が小さくなった) {
          となるようにソートする。
    
        // 重心( は除外)
          
    
         
        if   {
            // 反射
             
        } else if   {
            // 膨張
             
            if   {
                 
            } else {
                 
            }
        } else {
            // 収縮
             
            if   {
                 
            } else {
                 
            }
        }
    }
}

脚注

編集
  1. ^ Nelder, John A.; R. Mead (1965). “A simplex method for function minimization”. Computer Journal 7: 308–313. doi:10.1093/comjnl/7.4.308.