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

孤立全局最小值

打开实时脚本

难以定位的全局最小值

当吸引域较小或您不确定最小值的位置时，在全局最小值的吸引域中找到起点可能会很困难。要解决此类问题，您可以：

  • 添加合理的边界

  • 选取大量随机起点

  • 制作一个有序的起点网格

  • 对于无约束问题，取广泛分散的随机起点

这个示例展示了这些方法和一些变体。

对于所有 |x|>5 和 -sech(0)=-1，函数 -sech(x) 都接近零。该示例是 sech 函数的二维版本，其一个极小值位于 [1,1]，另一个位于 [1e5,-1e5]：

f(x,y)=-10sech(‖(x,y)-(1,1)‖)-20sech(0.003(‖(x,y)-(1e5,-1e5)‖))

f 在 (1e5,-1e5) 处具有全局最小值-21，在 (1,1) 处具有局部最小值 -11。

x1 = [1,1]; x2 = [1e5,-1e5];
% f is a vectorized version of the objective function
% Each row of an input matrix x is one point to evaluate
f = @(x,y)-10*sech(sqrt((x-x1(1)).^2+(y-x1(2)).^2)) ...
    -20*sech(3e-4*sqrt((x-x2(1)).^2+(y-x2(2)).^2))-1;
hndl = fsurf(@(x,y)f(x,y),[-1e6 1e6]);
zlim([-20,0])
set(hndl,LineStyle="none")
view(-45,10)
hold on
annotation("textarrow",...
    [0.71 0.56],[0.48 0.21],TextEdgeColor="none",...
    String="Global Minimum");
annotation("textarrow",...
    [.4,.52],[.6,.6],TextEdgeColor="none",...
    String="Local Minimum");
hold off

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

(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×2

    1.0000    1.0000


fval = 
-11.0000

具有边界和更多起点的全局搜索

为了找到全局最小值，您可以搜索更多的点。此示例使用 1e5 个起点和 300 秒的 MaxTime：

gs.NumTrialPoints = 1e5;
gs.MaxTime = 300;
[xg,fvalg] = run(gs,problem)
GlobalSearch stopped because it analyzed all the trial points.

4389 out of 4941 local solver runs converged with a positive local solver exit flag.

xg = 1×2
104 ×

   10.0000  -10.0000


fvalg = 
-21.0000

在此示例中，GlobalSearch 找到了全局最小值。

具有边界和多个起点的 MultiStart

或者，您可以使用具有多个起点的 MultiStart 进行搜索。此示例使用 1e5 个起点和 300 秒的 MaxTime：

ms = MultiStart(gs);
[xm,fvalm] = run(ms,problem,1e5)
MultiStart completed some of the runs from the start points. 

99996 out of 100000 local solver runs converged with a positive local solver exitflag.

xm = 1×2

    1.0000    1.0000


fvalm = 
-11.0000

在此示例中，MultiStart 无法找到全局最小值。

没有边界且起点分布广泛的 MultiStart

您还可以使用 MultiStart 搜索无界区域来找到全局最小值。再次，您需要许多起点才有机会找到全局最小值。

前五行代码使用 中描述的方法生成 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 exitflag.

xcust = 2×1
105 ×

    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 40401 local solver runs converged with a positive local solver exitflag.

xgrid = 2×1

      100000
     -100000


fgrid = 
-21

在此示例中，MultiStart 找到了全局最小值。

具有规则网格和良好起点的 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 exitflag.

xfew = 1×2

      100000     -100000


ffew = 
-21

在此示例中，MultiStart 找到了全局最小值。smallstartset 中只有两个起点，其中一个是全局最小值。

另请参阅

主题