このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

グローバル最適化とは何ですか?

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

最適化とは、関数を最小化する点を見つけるプロセスです。具体的には次のとおりです。

• 関数の 局所的 最小値とは、関数の値が近くの点の値以下であるが、遠い点よりも大きくなる可能性がある点です。

• グローバル最小値とは、関数の値が他のすべての実行可能な点の値よりも小さいか等しい点です。

一般的に、Optimization Toolbox™ ソルバーは局所最適値を見つけます。(この局所最適値は、全体最適値にもなり得ます。)彼らは出発点の吸引域内で最適値を見つけます。詳細については、引き込み領域を参照してください。

対照的に、Global Optimization Toolbox ソルバーは、複数の吸引域を検索するように設計されています。さまざまな方法で検索します。

• GlobalSearch と MultiStart は、いくつかの開始点を生成します。次に、ローカル ソルバーを使用して、開始点の吸引域内で最適値を見つけます。

• ga は、一連の開始点 (集団と呼ばれる) を使用し、集団からより良いポイントを繰り返し生成します。初期集団が複数の流域をカバーしている限り、ga は複数の流域を調査できます。

• particleswarm は、ga と同様に、一連の開始点を使用します。particleswarm は、人口が多様であるため、一度に複数の流域を調べることができます。

• simulannealbnd はランダム検索を実行します。一般的に、simulannealbnd は、前の点よりも良い点であれば受け入れます。simulannealbnd は、別の盆地に到達するために、時々、悪い点を受け入れます。

• patternsearch は、隣接するポイントをいくつか調べてから、そのうちの 1 つを受け入れます。いくつかの隣接するポイントが異なる盆地に属している場合、patternsearch は本質的に一度に複数の盆地を調べます。

• surrogateopt は、境界内で準ランダム サンプリングを行い、目的関数の値が小さいものを探します。surrogateopt は、評価ポイントから遠いポイントを優先する メリット関数 を使用し、グローバル ソリューションに到達しようとします。現在のポイントを改善できない場合、surrogateopt はリセットされ、再び境界内で広範囲にサンプリングが行われます。リセットは、surrogateopt がグローバル ソリューションを検索するもう 1 つの方法です。

引き込み領域

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

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

t が大きくなるにつれて局所最小値に向かうパス x(t) が生成されます。一般的に、互いに近い初期値 x(0) は、同じ最小点に向かう最も急な降下経路を与えます。最急降下法の 吸引域 は、同じ局所的最小値に至る初期値の集合です。

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

次の図は、最急降下経路が次元数が増えるにつれてどのように複雑になるかを示しています。

次の図は、さらに複雑な経路と吸引域を示しています。

制約は 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) のどちらかです。

関連するトピック

• 引力の盆地を視覚化する
• 6つのソルバーの比較