非線形関数の最適化

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 と似ていますが、多変数の関数を処理する点が異なります。初期区間ではなく開始ベクトル x₀ を指定します。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.6、y = -1.2、z = 0.135 を開始値として、この関数の最小値を検出します。

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

a =
    0.0000   -1.5708    0.1803

メモ

最適化ソルバーは実数値の関数に適用されます。ノルムなどの複素数値の実数値関数を除いて、複素数値を最適化することはできません。

関数を最大化

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

$\max_{x} f (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 点のシンプレックスを使用します。このアルゴリズムはまず、x₀(i) の各成分の 5% を x₀ に加算することで、初期推定値 x₀ の周りにシンプレックスを作成します。このアルゴリズムは、x₀ だけでなく、これらの n ベクトルをシンプレックスの要素として使用します (x₀(i) = 0 の場合、i の要素として 0.00025 を使用します)。次にアルゴリズムは以下の手順に繰り返し従い、シンプレックスを変更します。

メモ

fminsearch の反復表示のキーワードを手順の説明の後に [太字] で示します。

x(i) によって、現在のシンプレックスの点のリスト i = 1,...,n + 1 を示します。
最小の関数値 f(x(1)) から最大の関数値 f(x(n + 1)) へシンプレックスの点を並べます。反復の各ステップにおいて、アルゴリズムは現在の最悪の点 x(n + 1) を捨て、他の点をシンプレックスにします (あるいは手順 7 の場合、f(x(1)) より大きい値をもつすべての n 点を変更します)。
反射点を生成します。
r = 2m – x(n + 1), (1)
ここで以下のようになります。
m = Σx(i)/n, i = 1...n, (2)
f(r) を計算します。
f(x(1)) ≤ f(r) < f(x(n)) の場合、r を採用し、この反復を終了します。[反射]
f(r) < f(x(1)) の場合、拡張点 s を計算します。
s = m + 2(m – x(n + 1)), (3)
そして f(s) を計算します。
1. f(s) < f(r) の場合、s を採用してこの反復を終了します。[拡張]
2. そうでない場合は r を採用し、この反復を終了します。[反射]
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 (4)
  そして f(c) を計算します。f(c) < f(r) の場合、c を採用してこの反復を終了します。[外側に伸縮]
  そうでない場合は手順 7 (収縮) に進みます。
2. f(r) ≥ f(x(n + 1)) の場合は以下を計算します。
  cc = m + (x(n + 1) – m)/2 (5)
  そして f(cc) を計算します。f(cc) < f(x(n + 1)) の場合、cc を採用してこの反復を終了します。[内側に伸縮]
  そうでない場合は手順 7 (収縮) に進みます。
n 点を計算します。
v(i) = x(1) + (x(i) – x(1))/2 (6)
次に f(v(i)), i = 2,...,n + 1 を計算します。次の反復でのシンプレックスは x(1), v(2),...,v(n + 1) です。[収縮]

以下は、新しい各シンプレックスに対して、上記手順で関数 fminsearch によって計算できる点の図です。元のシンプレックスは太い外側の線です。反復は条件を満たすまで行われます。

Graphical representation of fminsearch algorithm showing reflection, expansion, contraction, and shrinking points.

参照

[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.