本页采用了机器翻译。点击此处可查看最新英文版本。

寻找全局或多个局部最小值

打开实时脚本

这个例子说明了 GlobalSearch 如何有效地找到全局最小值，以及 MultiStart 如何找到更多局部极小值。

此例的目标函数有许多局部极小值和一个唯一的全局最小值。在极坐标中，该函数为

f(r,t)=g(r)h(t)

其中

g(r)=(sin(r)-sin(2r)2+sin(3r)3-sin(4r)4+4)r2r+1h(t)=2+cos(t)+cos(2t-12)2.

绘制函数 g 和 h，并创建函数 f 的曲面图。

figure
subplot(1,2,1);
fplot(@(r)(sin(r) - sin(2*r)/2 + sin(3*r)/3 - sin(4*r)/4 + 4) .* r.^2./(r+1), [0 20])
title(''); ylabel('g'); xlabel('r');
subplot(1,2,2);
fplot(@(t)2 + cos(t) + cos(2*t-1/2)/2, [0 2*pi])
title(''); ylabel('h'); xlabel('t');

Figure contains 2 axes objects. Axes object 1 with xlabel r, ylabel g contains an object of type functionline. Axes object 2 with xlabel t, ylabel h contains an object of type functionline.

figure
fsurf(@(x,y) sawtoothxy(x,y), [-20 20])
% sawtoothxy is defined in the first step below
xlabel('x'); ylabel('y'); title('sawtoothxy(x,y)');
view(-18,52)

Figure contains an axes object. The axes object with title sawtoothxy(x,y), xlabel x, ylabel y contains an object of type functionsurface.

全局最小值位于 r = 0，目标函数为 0。函数 g(r) 在 r 中近似线性增长，具有重复的锯齿形状。函数 h(t) 有两个局部极小值，其中一个是全局。

sawtoothxy.m 文件从笛卡尔坐标转换为极坐标，然后计算极坐标中的值。

type sawtoothxy
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

通过 GlobalSearch 实现单一全局最小值

要使用 GlobalSearch 搜索全局最小值，首先创建一个问题结构体。对 fmincon 使用 'sqp' 算法，

problem = createOptimProblem('fmincon',...
    'objective',@(x)sawtoothxy(x(1),x(2)),...
    'x0',[100,-50],'options',...
    optimoptions(@fmincon,'Algorithm','sqp','Display','off'));

起点是 [100,-50] 而不是 [0,0]，所以 GlobalSearch 不是从全局解开始的。

通过运行 fmincon 来验证问题结构体。

[x,fval] = fmincon(problem)
x = 1×2

   45.7236 -107.6515


fval = 
555.5820

创建 GlobalSearch 对象，并设置迭代显示。

gs = GlobalSearch('Display','iter');

为了实现可再现性，请设置随机数生成器种子。

rng(14,'twister')

运行求解器。

[x,fval] = run(gs,problem)
 Num Pts                 Best       Current    Threshold        Local        Local                 
Analyzed  F-count        f(x)       Penalty      Penalty         f(x)     exitflag        Procedure
       0      200       555.6                                   555.6            0    Initial Point
     200     1463   1.547e-15                               1.547e-15            1    Stage 1 Local
     300     1564   1.547e-15     5.858e+04        1.074                              Stage 2 Search
     400     1664   1.547e-15      1.84e+05         4.16                              Stage 2 Search
     500     1764   1.547e-15     2.683e+04        11.84                              Stage 2 Search
     600     1864   1.547e-15     1.122e+04        30.95                              Stage 2 Search
     700     1964   1.547e-15     1.353e+04        65.25                              Stage 2 Search
     800     2064   1.547e-15     6.249e+04        163.8                              Stage 2 Search
     900     2164   1.547e-15     4.119e+04        409.2                              Stage 2 Search
     950     2359   1.547e-15           477        589.7          387            2    Stage 2 Local
     952     2423   1.547e-15         368.4          477        250.7            2    Stage 2 Local
    1000     2471   1.547e-15     4.031e+04        530.9                              Stage 2 Search

GlobalSearch stopped because it analyzed all the trial points.

3 out of 4 local solver runs converged with a positive local solver exit flag.

x = 1×2
10-7 ×

    0.0414    0.1298


fval = 
1.5467e-15

求解器找到三个局部极小值，包括 [0,0] 附近的全局最小值。

通过 MultiStart 找到多个局部最小值

要使用 MultiStart 搜索多个极小值，首先要创建一个问题结构体。由于该问题无约束，因此使用 fminunc 求解器。设置选项以在命令行上不显示任何显示。

problem = createOptimProblem('fminunc',...
    'objective',@(x)sawtoothxy(x(1),x(2)),...
    'x0',[100,-50],'options',...
    optimoptions(@fminunc,'Display','off'));

通过运行来验证问题结构体。

[x,fval] = fminunc(problem)
x = 1×2

    8.4420 -110.2602


fval = 
435.2573

创建一个默认的 MultiStart 对象。

ms = MultiStart;

运行求解器 50 次迭代，记录局部极小值。

rng(1) % For reproducibility
[x,fval,eflag,output,manymins] = run(ms,problem,50)
MultiStart completed some of the runs from the start points. 

10 out of 50 local solver runs converged with a positive local solver exitflag.

x = 1×2

  -73.8348 -197.7810


fval = 
766.8260

eflag = 
2

output = struct with fields:
                funcCount: 8574
         localSolverTotal: 50
       localSolverSuccess: 10
    localSolverIncomplete: 40
    localSolverNoSolution: 0
                  message: 'MultiStart completed some of the runs from the start points. ↵↵10 out of 50 local solver runs converged with a positive local solver exitflag.'


manymins=1×10 GlobalOptimSolution array with properties:
    X
    Fval
    Exitflag
    Output
    X0

求解器未找到 [0,0] 附近的全局最小值。求解器找到 10 个不同的局部极小值。

绘制局部极小值处的函数值：

histogram([manymins.Fval],10)

Figure contains an axes object. The axes object contains an object of type histogram.

在三个最佳点处绘制函数值：

bestf = [manymins.Fval];
histogram(bestf(1:3),10)

Figure contains an axes object. The axes object contains an object of type histogram.

MultiStart 从起点开始 fminunc，分量均匀分布在 -1000 到 1000 之间。fminunc 经常会卡在众多局部极小值之一。fminunc 超出其迭代限制或函数评估限制 40 次。

另请参阅

| |

主题