コンテンツにスキップ

ネルダー–ミード法

出典: フリー百科事典『ウィキペディア(Wikipedia)』

ネルダー–ミード法(ネルダー–ミードほう、: 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.