孤立したグローバル最小値

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

見つけにくいグローバル最小値

大域最小値の引力域内の開始点を見つけることは、その域が小さい場合や最小値の位置が不明な場合には困難になることがあります。この種の問題を解決するには、次の方法があります。

適切な境界を追加する
膨大な数のランダムなスタートポイントを取る
スタート地点を系統的にグリッド化する
制約のない問題の場合、広範囲に分散したランダムな開始点を取る

この例では、これらの方法といくつかのバリエーションを示します。

関数 –sech(x) は、すべての |x| > 5 および –sech(0) = –1 に対してほぼ 0 になります。この例は sech 関数の 2 次元バージョンであり、1 つの最小値は [1,1] に、もう 1 つは [1e5,-1e5] にあります。

f(x,y) = –10sech(|x – (1,1)|) – 20sech(.0003(|x – (1e5,–1e5)|) – 1.

fは(1e5,-1e5)で-21の大域的最小値を持ち、(1,1)で-11の局所的最小値を持ちます。

図を生成するコード

(1e5,–1e5) の最小値は狭いスパイクとして表示されます。(1,1) の最小値は狭すぎるため表示されません。

次のセクションでは、グローバル最小値を検索するさまざまな方法を示します。いくつかの方法はこの問題には効果がありません。それでも、それぞれの方法がさまざまな問題に役立つことがわかるかもしれません。

デフォルト設定ではグローバル最小値を見つけることができません - 境界を追加

GlobalSearch と MultiStart は、デフォルトのグローバルオプションを使用してグローバル最小値を見つけることができません。これは、デフォルトの開始点コンポーネントが、GlobalSearch の場合は (–9999,10001) の範囲内、MultiStart の場合は (–1000,1000) の範囲内にあるためです。

problem に –1e6 と 1e6 という追加の境界があるため、GlobalSearch は通常、大域的最小値を見つけられません。

x1 = [1;1];x2 = [1e5;-1e5];
f = @(x)-10*sech(norm(x(:)-x1)) -20*sech((norm(x(:)-x2))*3e-4) -1;
opts = optimoptions(@fmincon,'Algorithm','active-set');
problem = createOptimProblem('fmincon','x0',[0,0],'objective',f,...
    'lb',[-1e6;-1e6],'ub',[1e6;1e6],'options',opts);
gs = GlobalSearch;
rng(14,'twister') % for reproducibility
[xfinal,fval] = run(gs,problem)

GlobalSearch stopped because it analyzed all the trial points.

All 32 local solver runs converged with a positive 
local solver exit flag.

xfinal =
    1.0000    1.0000

fval =
  -11.0000

境界と開始点を追加した GlobalSearch

グローバル最小値を見つけるには、より多くのポイントを検索できます。この例では、1e5 の開始点と 300 秒の MaxTime を使用します。

gs.NumTrialPoints = 1e5;
gs.MaxTime = 300;
[xg,fvalg] = run(gs,problem)

GlobalSearch stopped because maximum time is exceeded.

GlobalSearch called the local solver 2186 times before exceeding 
the clock time limit (MaxTime = 300 seconds).
1943 local solver runs converged with a positive 
local solver exit flag.

xg =
   1.0e+04 *
   10.0000  -10.0000

fvalg =
  -21.0000

この場合、GlobalSearch はグローバル最小値を見つけました。

境界と多数の開始点を持つマルチスタート

あるいは、多くの開始点を持つ MultiStart を使用して検索することもできます。この例では、1e5 の開始点と 300 秒の MaxTime を使用します。

ms = MultiStart(gs);
[xm,fvalm] = run(ms,problem,1e5)

MultiStart stopped because maximum time was exceeded.

MultiStart called the local solver 17266 times before exceeding
the clock time limit (MaxTime = 300 seconds).
17266 local solver runs converged with a positive 
local solver exit flag.

xm =
    1.0000    1.0000

fvalm =
  -11.0000

この場合、MultiStart はグローバル最小値を見つけることができませんでした。

境界のないマルチスタート、広範囲に分散したスタートポイント

MultiStart を使用して、境界のない領域を検索し、グローバル最小値を見つけることもできます。繰り返しになりますが、グローバル最小値を見つける可能性を高めるには、多くの開始点が必要です。

コードの最初の 5 行は、制約のないコンポーネントの広範囲に分散したポイントで説明されている方法を使用して、広範囲に分散した 10,000 個のランダムな開始点を生成します。newprob は、fminunc ローカルソルバーを使用し、境界のない問題構造です。

rng(0,'twister') % for reproducibility
u = rand(1e4,1);
u = 1./u;
u = exp(u) - exp(1);
s = rand(1e4,1)*2*pi;
stpts = [u.*cos(s),u.*sin(s)];
startpts = CustomStartPointSet(stpts);

opts = optimoptions(@fminunc,'Algorithm','quasi-newton');
newprob = createOptimProblem('fminunc','x0',[0;0],'objective',f,...
    'options',opts);
[xcust,fcust] = run(ms,newprob,startpts)

MultiStart completed the runs from all start points.

All 10000 local solver runs converged with a positive
local solver exit flag.

xcust =
   1.0e+05 *

    1.0000
   -1.0000

fcust =
  -21.0000

この場合、MultiStart はグローバル最小値を見つけました。

スタートポイントの規則的なグリッドを持つマルチスタート

ランダムな開始点の代わりに、開始点のグリッドを使用することもできます。より多くの次元、または小さな摂動を持つ規則的なグリッドを構築する方法については、等間隔グリッドまたは乱れたグリッドを参照してください。

xx = -1e6:1e4:1e6;
[xxx,yyy] = meshgrid(xx,xx);
z = [xxx(:),yyy(:)];
bigstart = CustomStartPointSet(z);
[xgrid,fgrid] = run(ms,newprob,bigstart)

MultiStart completed the runs from all start points.

All 10000 local solver runs converged with a positive 
local solver exit flag.

xgrid =
  1.0e+004 *

   10.0000
  -10.0000

fgrid =
  -21.0000

この場合、MultiStart はグローバル最小値を見つけました。

通常のグリッドと有望な開始点を備えたマルチスタート

特に高次元の場合、開始点の規則的なグリッドを作成すると、膨大な量のメモリや時間がかかる可能性があります。開始ポイントをフィルタリングして、目的関数の値が小さいものだけを実行することができます。

このフィルタリングを最も効率的に実行するには、目的関数をベクトル化された形式で記述します。詳細については、ベクトル化された関数を書くまたは目的関数と制約関数をベクトル化するを参照してください。次の関数ハンドルは、行が開始点を表す入力行列に基づいて目的のベクトルを計算します。

x1 = [1;1];x2 = [1e5;-1e5];
g = @(x) -10*sech(sqrt((x(:,1)-x1(1)).^2 + (x(:,2)-x1(2)).^2)) ...
     -20*sech(sqrt((x(:,1)-x2(1)).^2 + (x(:,2)-x2(2)).^2))-1;

値が -2 未満のポイントに対してのみローカルソルバーを実行するとします。スタートポイントの規則的なグリッドを持つマルチスタートよりも密度の高いグリッドから始めて、関数値の高いすべてのポイントを除外します。

xx = -1e6:1e3:1e6;
[xxx,yyy] = meshgrid(xx,xx);
z = [xxx(:),yyy(:)];
idx = g(z) < -2; % index of promising start points
zz = z(idx,:);
smallstartset = CustomStartPointSet(zz);
opts = optimoptions(@fminunc,'Algorithm','quasi-newton','Display','off');
newprobg = createOptimProblem('fminunc','x0',[0,0],...
    'objective',g,'options',opts); 
    % row vector x0 since g expects rows
[xfew,ffew] = run(ms,newprobg,smallstartset)

MultiStart completed the runs from all start points.

All 2 local solver runs converged with a positive 
local solver exit flag.

xfew =
      100000     -100000

ffew =
   -21

この場合、MultiStart はグローバル最小値を見つけました。smallstartset には開始点が 2 つしかなく、そのうちの 1 つがグローバル最小値です。