最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

fminsearch アルゴリズム

fminsearch は、Lagarias らの [57] で説明されている Nelder-Mead のシンプレックス アルゴリズムを使用します。このアルゴリズムは n 次元のベクトル x に対して、n + 1 点のシンプレックスを使用します。このアルゴリズムはまず始めに、x0(i) の要素の 5% を x0 に加え、これらの n ベクトルをx0 に付け加えてシンプレックスの要素として使用し、初期推定 x0 のまわりにシンプレックスを作成します(x0(i) = 0 の場合、要素 i として 0.00025 を使用します)。次にアルゴリズムは以下の手順に従い、シンプレックスを繰り返し変更します。

メモ

fminsearch 反復表示のためのキーワードは、手順の説明後に [ ] 付きで表示されます。

  1. x(i) が現在のシンプレックスの点のリスト i = 1,...,n+1 を示すとします。

  2. 最小の関数値 f(x(1)) から最大の関数値 f(x(n+1)) へシンプレックスの点を並べます。反復の各ステップにおいて、アルゴリズムは現在の最悪の点 x(n+1) を破棄し、他の点をシンプレックスにします (あるいは、次の手順 7 の場合に、f(x(1)) より大きい値をもつすべての n 点が変更されます)。

  3. 反射点の生成

    r = 2m – x(n+1)

    ここで、

    m = Σx(i)/n, i = 1...n

    そして、f(r) を計算します。

  4. f(x(1)) ≤ f(r) < f(x(n)) の場合、r を採用し、この反復を終了します。[反射]

  5. f(r) < f(x(1)) の場合、拡張点 s を計算し、

    s = m + 2(m – x(n+1))

    そして、f(s) を計算します。

    1. f(s) < f(r) の場合、s を採用してこの反復を終了します。[展開]

    2. そうでない場合は r を採用し、この反復を終了します。[反射]

  6. f(r) ≥ f(x(n)) の場合、x(n+1) と r の良い方の値と m の間で縮小を実行します。

    1. f(r)< f(x(n+1)) (すなわち、r が x(n+1)) より良い場合は、

      c = m + (r – m)/2

      と、f(c) を計算します。f(c) < f(r) の場合、c を採用してこの反復を終了します。[外側に縮小] そうでない場合は、手順 7 (収縮) を続行します。

    2. f(r)≥ f(x(n+1)) の場合、

      cc = m + (x(n+1) – m)/2

      そして、f(cc) を計算します。f(cc) < f(x(n+1)) の場合、cc を採用してこの反復を終了します。[内側に縮小] そうでない場合は、手順 7 (収縮) を続行します。

  7. n 点を計算します

    v(i) = x(1) + (x(i) – x(1))/2

    そして、f(v(i)) (i = 2,...,n+1) を計算します。次の反復でシンプレックスは x(1), v(2),...,v(n+1) です。[収縮]

以下の図は、fminsearch が新しい各シンプレックスと共にステップで計算するであろう点を示します。元のシンプレックスは太い外側の線で示されます。反復は停止条件を満たすまで行われます。

参考

関連するトピック