非線形関数の最適化
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.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
のソルバーは目的関数を最小化しようとします。最大化問題を扱う場合、問題の形式は次のとおりです。
形式を 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
の反復表示のキーワードを手順の説明の後に [太字] で示します。
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) を計算します。
f(s) < f(r) の場合、s を採用してこの反復を終了します。[拡張]
そうでない場合は r を採用し、この反復を終了します。[反射]
f(r) ≥ f(x(n)) の場合、x(n + 1) と r で目的関数の値が低い方と m の間で "伸縮" を実行します。
f(r) < f(x(n + 1)) (すなわち、r が x(n + 1) よりも良好) の場合は、次を計算します。
c = m + (r – m)/2 (4) そして f(c) を計算します。f(c) < f(r) の場合、c を採用してこの反復を終了します。[外側に伸縮]
そうでない場合は手順 7 (収縮) に進みます。
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
によって計算できる点の図です。元のシンプレックスは太い外側の線です。反復は条件を満たすまで行われます。
参照
[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.
関連するトピック
- 最適化のトラブルシューティングとヒント
- 非線形最適化 (Optimization Toolbox)
- 最適化を介して曲線近似