大域的最適解と局所的最適解

ソルバーが最小の最小値を見つけられない理由

一般的に、ソルバーは局所的最小値 (または最適解) を返します。結果が大域的最小値 (または最適解) である可能性はありますが、この結果は保証されません。

• 関数の "局所的" 最小値は、近傍の点の中ではその関数値が最小であっても、離れた点よりも大きい可能性があります。

• "大域的" 最小値は、その関数値が他のすべての実行可能点よりも小さい点です。

Optimization Toolbox™ のソルバーは通常、局所的最小値を探索します (この局所的最小値は大域的最小値であるかもしれません)。ソルバーは開始点の "引き込み領域" 内で最小値を見つけます。引き込み領域については、引き込み領域を参照してください。

以下は、この一般的な規則の例外です。

• 線形計画問題と正定値二次計画問題は凸可能領域をもつ凸計画問題であるため、引き込み領域は 1 つのみとなります。指定したオプションによっては linprog はユーザーが指定したすべての初期点を無視します。quadprog に初期点は必要ありませんが、初期点を与えることによって最小化が高速化される場合があります。

• simulannealbnd などのような、Global Optimization Toolbox の関数は、複数の引き込み領域を検索しようとします。

より小さい最小値の検索

大域的最小値が必要な場合、大域的最小値が含まれている引き込み領域内でソルバーの開始値を検索しなければなりません。

以下のように、開始値を設定して大域的最小値を検索できます。

• 規則的な格子状に初期点を指定します。

• 問題の座標がすべて有界である場合は、一様分布から選ばれた無作為な点を使用します。いくつかの成分が非有界の場合は、正規分布、指数分布、他のランダム分布から取得された点を使用します。大域的最小値の位置を予測できない場合は、使用するランダム分布を広げます。たとえば、正規分布は平均から 3 以上の標準偏差のサンプルはめったにありませんが、コーシー分布 (密度 1/(π(1 + x²))) は広範囲にサンプルを分散させることができます。

• 各座標に対して、正規分布、指数分布、その他の確率分布に無作為な摂動を加えた初期点を使用します。

• Global Optimization Toolbox ライセンスをお持ちの場合は、GlobalSearch (Global Optimization Toolbox) または MultiStart (Global Optimization Toolbox) ソルバーを使用してください。これらのソルバーは、範囲内でランダムな開始点を自動的に生成します。

ある程度初期点が予測できる場合は、範囲を狭くすることでうまく探索することができます。

引き込み領域

目的関数 f(x) が滑らかな場合、ベクトル –∇f(x) は f(x) が最も急激に減少する方向を示します。最急降下の式は以下のようになります。

$$\frac{d}{dt}x(t)=-\nabla f(x(t)),$$

これは t が増加するにつれて、局所的最小値へ到達する経路 x(t) を導きます。一般的に、開始値 x(0) に近い値は最急降下経路に沿って同じ最小値を求める傾向があります。最急降下法の引き込み領域は、同じ局所的最小値に導く開始値の集合です。

この図は 1 次元上の 2 個の最小値を示します。図は、異なる引き込み領域を別々のライン スタイルで示し、最急降下の方向を矢印で示します。この図と次の図の黒い点は、ローカルな最小値を示します。点 x(0) で始まる最急降下経路は、x(0) を含む引き込み領域の黒い点に向かいます。

1 次元領域

この図は、高次元になると最急降下の経路がより複雑になる可能性があることを示します。

さまざまな初期点からの最急降下経路を表す引き込み領域

この図はより複雑な経路と引き込み領域を示します。

複数の引き込み領域

制約は 1 つの引き込み領域をいくつかの断片に分割することがあります。たとえば、y の最小化を考えてみましょう。

y ≥ |x|

y ≥ 5 – 4(x–2)².

この図は最終点をもつ 2 つの引き込み領域を示します。

 図を生成するコード

myabs = @(x) abs(x);
mycurve = @(x) 5 - 4.*(x-2).^2;
myline = @(x) max(myabs(x),mycurve(x));
mybrdr = @(x) 1 + heaviside(x-2);
myarea = @(x,y) heaviside(y - myline(x)).*mybrdr(x);
% myarea = 0 where infeasible, 1 when x < 2, 2 when x > 2
marinv = @(x,y) 1./myarea(x,y); % removes the infeasible region

plot(0,0,'k.','MarkerSize',25,'LineWidth',2);
hold on
grid on
plot(11/4,11/4,'k.','MarkerSize',25,'LineWidth',2);
fplot(mycurve,'k',[.9 3],'LineWidth',2)
fplot(myline,[-2 5],'k','LineWidth',2)
fsurf(marinv,[-2 5 -1,6],'EdgeColor','none','FaceAlpha',0.5)
colormap jet

コマンド ラインで「plottools」と入力し、矢の描画ツールを使用して矢を追加します。

最急降下経路は制約境界までの直線です。制約境界から、最急降下経路は境界に沿って下に移動します。初期の x 値が 2 の上か下にあるかで異なりますが、最終点は (0,0) または (11/4,11/4) のどちらかです。

関連するトピック

• 結果の向上