ソリューションがグローバルであることを証明できますか?

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

保証なし

目的関数のグローバル最小値を見つけたかどうかはどうすればわかりますか?簡単に答えると、それはできません。Global Optimization Toolbox ソルバーの結果がグローバル最適値であるという保証はありません。すべての Global Optimization Toolbox ソルバーはグローバルソリューションの検索を繰り返し試みますが、ソリューションがグローバルであることを証明できるアルゴリズムを採用しているソルバーはありません。

ただし、このセクションの戦略を使用して解決策を調査することができます。

パターン検索を使用してソリューションがローカルソリューションであるかどうかを確認する

想定される解がグローバル最小値であるかどうかを判断する前に、まずそれがローカル最小値であるかどうかを確認します。これを行うには、問題に対して patternsearch を実行します。

problemをfminconやfminuncの代わりにpatternsearchを使用するように変換するには、次のように入力します。

problem.solver = 'patternsearch';

また、開始点を先ほど見つけた解決策に変更し、オプションをクリアします。

problem.x0 = x;
problem.options = [];

たとえば、近くのポイントを確認では次のように表示されます。

options = optimoptions(@fmincon,'Algorithm','active-set');
ffun = @(x)(x(1)-(x(1)-x(2))^2);
problem = createOptimProblem('fmincon', ...
    'objective',ffun,'x0',[1/2 1/3], ...
    'lb',[0 -1],'ub',[1 1],'options',options);
[x,fval,exitflag] = fmincon(problem)

x =
  1.0e-007 *
         0    0.1614

fval =
 -2.6059e-016

exitflag =
     1

しかし、この解決策を patternsearch で確認すると、より良い解決策があることがわかります。報告されたソリューション x から patternsearch を開始します。

% set the candidate solution x as the start point
problem.x0 = x;
problem.solver = 'patternsearch';
problem.options = [];
[xp,fvalp,exitflagp] = patternsearch(problem)

Optimization terminated: mesh size less than options.MeshTolerance.

xp =

    1.0000   -1.0000


fvalp =

   -3.0000


exitflagp =

     1

グローバルソリューションを含む境界領域を特定する

境界のある領域に滑らかな目的関数があるとします。十分な時間と開始点が与えられれば、MultiStart は最終的にグローバルソリューションを見つけます。

したがって、グローバルソリューションが存在できる領域を境界で囲むことができれば、MultiStart がグローバルソリューションを特定するというある程度の保証を得ることができます。

例えば、関数

$f = x^{6} + y^{6} + \sin (x + y) (x^{2} + y^{2}) - \cos (\frac{x^{2}}{1 + y^{2}}) (2 + x^{4} + x^{2} y^{2} + y^{4}) .$

最初の加数 x⁶ + y⁶ は、|x| または |y| の値が大きい場合に関数を大きくして正になるように強制します。関数の最小値の成分は境界内になければならない

–10 ≤ x,y ≤ 10,

10⁶ は、関数の他の加数に現れる 10⁴ のすべての倍数よりもはるかに大きいからです。

この問題では、より小さい境界を特定できます。たとえば、グローバル最小値は -2 から 2 の間です。最良の境界を特定することよりも、合理的な境界を特定することの方が重要です。

複数の開始ポイントでマルチスタートを使用する

問題に対するより良い解決策があるかどうかを確認するには、追加の開始ポイントを指定して MultiStart を実行します。GlobalSearch ではローカルソルバーがすべての開始点から実行されないため、このタスクでは GlobalSearch ではなく MultiStart を使用します。

例については、例: より良い解決策を求めてを参照してください。