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

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

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

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

其中

$\begin{array}{l} g (r) = (\sin (r) - \frac{\sin (2 r)}{2} + \frac{\sin (3 r)}{3} - \frac{\sin (4 r)}{4} + 4) \frac{r^{2}}{r + 1} \\ h (t) = 2 + \cos (t) + \frac{\cos (2 t - \frac{1}{2})}{2} . \end{array}$

绘制函数 $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
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)

全局最小值位于 $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. ...'

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

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

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

histogram([manymins.Fval],10)

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

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

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

另请参阅

GlobalSearch | MultiStart | createOptimProblem

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

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

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

另请参阅

相关主题

WeChat

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

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