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

孤立全局最小值

难以定位的全局最小值

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

  • 添加合理的边界

  • 选取大量随机起点

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

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

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

对于所有 –sech(x) 和 |x| > 5，函数 –sech(0) = –1 几乎为 0。该示例是 sech 函数的二维版本，其中一个最小值在 [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

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

为了找到全局最小值，您可以搜索更多的点。此示例使用 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

或者，您可以使用具有多个起点的 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

您还可以使用 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 exit flag.

xcust =
   1.0e+05 *

    1.0000
   -1.0000

fcust =
  -21.0000

在这种情况下，MultiStart 找到了全局最小值。

具有起点规则网格的 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 找到了全局最小值。

具有规则网格和良好起点的 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 的点运行局部求解器。从比 具有起点规则网格的 MultiStart 更密集的网格开始，然后过滤掉所有具有高函数值的点：

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 中只有两个起点，其中一个是全局最小值。

另请参阅

主题