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

patternsearch を用いた大域的最小値の探索

ライブ スクリプトを開く

patternsearch ソルバーは必ずしも大域的最小値に収束するとは限りません。大域的最小値を取得する可能性を高めるには、ランダムな開始点から patternsearch を複数回再起動します。

複数の局所最小値の問題

sawtoothxy 関数には複数の局所最小値があり、関数値が 0 である [0,0] に大域的最小値があります。

function f = sawtoothxy(x,y)
[t,r] = cart2pol(x,y); % change to polar coordinates
h = cos(2*t - 1/2)/2 + cos(t) + 2;
g = (sin(r) - sin(2*r)/2 + sin(3*r)/3 - sin(4*r)/4 + 4) ...
    .*r.^2./(r+1);
f = g.*h;
end

問題に対して非対称線形不等式制約を作成し、大域的最小値から離れた実行可能な初期点を作成します。

A = [1 1
    1 -1
    -1 1
    -1 -1];
b = [200,200,20,10];
fun = @(t)sawtoothxy(t(1),t(2));
rng(10) % Sets random number stream
x0 = [100,-50] + 10*randn(1,2);

初期点が実行可能であることを確認し、その点で sawtoothxy 関数を評価します。

A*x0' - b' % Should be negative for a feasible initial point.
ans = 4×1

 -158.1931
  -28.8906
 -191.1094
  -51.8069


fun(x0)
ans = 
1.1681e+03

patternsearch "nups" アルゴリズムは通常、効率的に適切なソリューションを見つけます。この問題に対してどのように機能するかを確認します。

options = optimoptions("patternsearch",Algorithm="nups");
[x,fval,eflag,output] = patternsearch(fun,x0,A,b,[],[],[],[],[],options)
patternsearch stopped because the mesh size was less than options.MeshTolerance.

x = 1×2

    0.0088  -10.0088


fval = 
35.2488

eflag = 
1

output = struct with fields:
         function: @(t)sawtoothxy(t(1),t(2))
      problemtype: 'linearconstraints'
       pollmethod: 'nups'
    maxconstraint: 0
     searchmethod: []
       iterations: 61
        funccount: 180
         meshsize: 6.7893e-07
         rngstate: [1×1 struct]
          message: 'patternsearch stopped because the mesh size was less than options.MeshTolerance.'

ソルバーは大域的最小値を見つけられません。ただし、別の開始点を選択すると、より良い結果が得られます。

x0 = [100,-50] + 10*randn(1,2); % New start point
[x,fval,eflag,output] = patternsearch(fun,x0,A,b,[],[],[],[],[],options)
patternsearch stopped because the mesh size was less than options.MeshTolerance.

x = 1×2
10-6 ×

    0.0247   -0.3333


fval = 
7.1681e-13

eflag = 
1

output = struct with fields:
         function: @(t)sawtoothxy(t(1),t(2))
      problemtype: 'linearconstraints'
       pollmethod: 'nups'
    maxconstraint: 0
     searchmethod: []
       iterations: 70
        funccount: 161
         meshsize: 9.6669e-07
         rngstate: [1×1 struct]
          message: 'patternsearch stopped because the mesh size was less than options.MeshTolerance.'

今回は、ソルバーは大域的最小値に到達します。ただし、別の問題の場合は、ソルバーを何度も再起動する必要がある場合があります。

ランダムポイントからソルバーを再開する

大域的最小値を探索するには、ランダムなポイントから patternsearch を繰り返し開始してみてください。問題がすべての変数に有限の境界を持つ場合、ランダムポイントを使用することができます。

x0 = lb + rand(size(lb)).*(ub - lb);

これらのポイントは境界内で均一にランダムに生成されます。

現在の問題には明確な境界がありません。ただし、線形制約により、サンプリングできる長方形の領域が提供されます。さらに便利なことに、変数 -15≤x≤200 と -105≤y≤110 の境界を推測できます。推定境界を次のように選択する

lb = [-15,-105];
ub = [200,110];

均一サンプラーを使用してランダムなポイントを繰り返し選択し、最良の結果を得るようにします。

N = 20; % Number of attempts to make.
rng(600) % Set a point that does not lead to the global minimum.
x0 = lb + rand(size(lb)).*(ub - lb);
options.Display = "none"; % Suppress output.
[x,fval,eflag,output] = patternsearch(fun,x0,A,b,[],[],[],[],[],options);
disp(fval) % Starting function value.
   35.2488

for i = 2:N
    x0 = lb + rand(size(lb)).*(ub - lb);
    [x2,fval2,eflag2,output2] = patternsearch(fun,x0,A,b,[],[],[],[],[],options);
    if fval2 < fval % Copy results to x, fval, eflag, output
        x = x2;
        fval = fval2;
        eflag = eflag2;
        output = output2;
    end
end
disp(fval)
     0

ソルバーは大域解に到達します。大域的最小値を探索する他の方法については、開始点を生成する方法 を参照してください。

参考

トピック