ネルダー–ミード法のソースを表示

'''ネルダー–ミード法'''（ネルダー–ミードほう、{{lang-en-short|Nelder–Mead method}}）や'''滑降シンプレックス法'''（{{lang-en-short|downhill simplex method}}）や'''アメーバ法'''（{{lang-en-short|amoeba method}}）は、[[最適化問題]]の[[アルゴリズム]]。導関数は不要。[[1965年]]に John A. Nelder と Roger Mead が発表した<ref name="NM">
{{cite journal | last = Nelder | first = John A. |author2=R. Mead | title = A simplex method for function minimization | journal = Computer Journal | volume = 7 | year = 1965 | pages = 308–313 | doi =  10.1093/comjnl/7.4.308}}</ref>。

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

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

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

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

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

== 脚注 ==
{{reflist}}

{{最適化アルゴリズム}}

{{Computer-stub|ねるたみとほう}}
{{DEFAULTSORT:ねるたみとほう}}

[[Category:最適化アルゴリズム]]
[[Category:数学に関する記事]]
[[Category:エポニム]]