Main Content

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

非線形関数の最適化

1 変数関数の最小化

1 変数の数学関数がある場合、関数 fminbnd を使用すると、指定範囲での関数の局所的最小点を求めることができます。たとえば、MATLAB® で提供されている関数 humps.m を考えてみましょう。次の図は humps のグラフを示しています。

x = -1:.01:2;
y = humps(x);
plot(x,y)
xlabel('x')
ylabel('humps(x)')
grid on

範囲 (0.3,1) における関数 humps の最小値を求めるには、以下を使用します。

x = fminbnd(@humps,0.3,1)
x = 0.6370

optimset を使用して、Display オプションが 'iter' に設定されたオプションを作成することで、求解プロセスの詳細を確認できます。結果のオプションを fminbnd に渡します。

options = optimset('Display','iter');
x = fminbnd(@humps,0.3,1,options)
 
 Func-count     x          f(x)         Procedure
    1       0.567376      12.9098        initial
    2       0.732624      13.7746        golden
    3       0.465248      25.1714        golden
    4       0.644416      11.2693        parabolic
    5         0.6413      11.2583        parabolic
    6       0.637618      11.2529        parabolic
    7       0.636985      11.2528        parabolic
    8       0.637019      11.2528        parabolic
    9       0.637052      11.2528        parabolic
 
Optimization terminated:
 the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-04 
x = 0.6370

反復表示は、関数評価ごとに x の現在値と関数値 f(x) を示したものです。関数 fminbnd では、1 つの関数評価はアルゴリズムの 1 回の反復に対応しています。最後の列は各反復で fminbnd が使用する、黄金分割探索または双曲線内挿の手続きを示しています。詳細については、最適化ソルバーの反復表示を参照してください。

多変数関数の最小化

関数 fminsearch は、fminbnd と似ていますが、多変数の関数を処理する点が異なります。初期区間ではなく開始ベクトル x0 を指定します。fminsearch は、この開始ベクトル近傍の数学関数の局所的最小点であるベクトル x を返そうとします。

3 変数 x, y, z の関数 three_var を作成し、関数 fminsearch を実行します。

function b = three_var(v)
x = v(1);
y = v(2);
z = v(3);
b = x.^2 + 2.5*sin(y) - z^2*x^2*y^2;

x = -0.6y = -1.2z = 0.135 を開始値として、この関数の最小値を検出します。

v = [-0.6,-1.2,0.135];
a = fminsearch(@three_var,v)

a =
    0.0000   -1.5708    0.1803

関数を最大化

関数 fminbnd と関数 fminsearch のソルバーは目的関数を最小化しようとします。最大化問題を扱う場合、問題の形式は次のとおりです。

maxxf(x),

形式を g(x) = –f(x) に定義しなおし、g を最小化します。

たとえば、x = 5 の近くの tan(cos(x)) の最大値を見つけるには以下を計算します。

[x fval] = fminbnd(@(x)-tan(cos(x)),3,8)

x =
    6.2832

fval =
   -1.5574

最大値は x = 6.2832 のとき 1.5574 (fval の出力の負の値) になります。この回答は 5 桁まで正しい結果です。最大値は x = 2π = 6.2832 のとき tan(1) = 1.5574 になります。

fminsearch アルゴリズム

fminsearch は、Lagarias et al.[1]で説明されている Nelder-Mead のシンプレックス アルゴリズムを使用します。このアルゴリズムは n 次元のベクトル x に対して、n+1 点のシンプレックスを使用します。このアルゴリズムはまず、x0(i) の各成分の 5% を x0 に加算することで、初期推定値 x0 の周りにシンプレックスを作成します。このアルゴリズムは、x0 だけでなく、これらの n ベクトルをシンプレックスの要素として使用します (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 によって計算できる点の図です。元のシンプレックスは太い外側の線です。反復は条件を満たすまで行われます。

参照

[1] Lagarias, J. C., J. A. Reeds, M. H. Wright, and P. E. Wright. “Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions.” SIAM Journal of Optimization, Vol. 9, Number 1, 1998, pp. 112–147.

関連するトピック