细化起点

关于优化起点

如果问题的某些分量无约束，GlobalSearch 和 MultiStart 将使用人工边界在每个分量中均匀地生成随机起点。但是，如果您的问题具有遥远的极小值，则需要广泛分散的起点来找到这些极小值。

使用这些方法可以获得广泛分散的起点：

在您的 problem 结构体中给出广泛分离的边界。
将 RandomStartPointSet 对象与 MultiStart 算法一起使用。在 RandomStartPointSet 对象中设置 ArtificialBound 属性的一个较大值。
将 CustomStartPointSet 对象与 MultiStart 算法一起使用。使用广泛分散的起点。

每种方法都有优点和缺点。

方法	优点	缺点
在 `problem` 中给出边界	自动生成点	制作更复杂的 Hessian
	可与 `GlobalSearch` 结合使用	不清楚该把边界设多大
	容易做到	变化 `problem`
	边界可能不对称	仅限均匀点
`RandomStartPointSet` 中的大 `ArtificialBound`	自动生成点	仅限 `MultiStart`
	不改变 `problem`	仅限对称、均匀的点
	容易做到	不清楚 `ArtificialBound` 应该设置多大
`CustomStartPointSet`	可自定义	仅限 `MultiStart`
`CustomStartPointSet`	不改变 `problem`	需要编程来生成点

均匀网格

要生成均匀的起点网格：

使用 ndgrid 生成多维数组。给出每个分量的下界、间距和上界。
例如，要生成一组三维数组
- 第一个分量从 -2 到 0，间距为 0.5
- 第二个分量从 0 到 2，间距 0.25
- 第三个分量从 -10 到 5，间距 1
```
[X,Y,Z] = ndgrid(-2:.5:0,0:.25:2,-10:5);
```
将数组放入单个矩阵中，每行代表一个起点。例如：
```
W = [X(:),Y(:),Z(:)];
```
在这个例子中，W 是一个 720×3 的矩阵。
将矩阵放入 CustomStartPointSet 对象中。例如：
```
custpts = CustomStartPointSet(W);
```

以 CustomStartPointSet 对象作为第三个输入来调用 run。例如，

% Assume problem structure and ms MultiStart object exist
[x,fval,flag,outpt,manymins] = run(ms,problem,custpts);

扰动网格

与稍微受干扰的起点相比，整数起点可能产生不太稳健的解。

要获得一组扰动的起点：

按照均匀网格的步骤 1-2 生成起点矩阵。
通过添加均值为 0 且方差相对较小的随机正态矩阵来扰乱起点。
对于均匀网格中的例子，在制作 W 矩阵后，添加一个扰动：
```
[X,Y,Z] = ndgrid(-2:.5:0,0:.25:2,-10:5);
W = [X(:),Y(:),Z(:)];
W = W + 0.01*randn(size(W));
```
将矩阵放入 CustomStartPointSet 对象中。例如：
```
custpts = CustomStartPointSet(W);
```

以 CustomStartPointSet 对象作为第三个输入来调用 run。例如，

% Assume problem structure and ms MultiStart object exist
[x,fval,flag,outpt,manymins] = run(ms,problem,custpts);

不受约束的组件的点分布广泛

问题的某些分量可能缺少下界。例如：

尽管没有明确的边界，但还是存在着分量无法达到的水平。例如，如果一个分量代表一颗钻石的重量，则隐含的上界是 1 公斤（希望钻石的重量低于 10 克）。在这种情况下，给出隐式边界作为上界。
确实没有上界。例如，计算机文件的大小（以字节为单位）没有有效的上界。如今最大的规模可以是千兆字节或兆兆字节，但 10 年后，谁知道呢？

对于真正无界分量，可以使用以下采样方法。要在每个区域 (exp(n),exp(n+1)) 中生成大约 1/n 个点，请使用以下公式。如果 u 是随机的并且从 0 到 1 均匀分布，那么 r = 2u – 1 就是在 -1 和 1 之间均匀分布。取

$y = sgn (r) (\exp (1 / | r |) - e) .$

y 是对称且随机的。对于由 lb 限定的变量，取

$y = lb + (\exp (1 / u) - e) .$

类似地，对于 ub 上方有界的变量，取

$y = ub - (\exp (1 / u) - e) .$

例如，假设您有一个三维问题

x(1) > 0
x(2) < 100
x(3) 无约束

为了使 150 个起点满足以下约束：

u = rand(150,3);
r1 = 1./u(:,1);
r1 = exp(r1) - exp(1);
r2 = 1./u(:,2);
r2 = -exp(r2) + exp(1) + 100;
r3 = 1./(2*u(:,3)-1);
r3 = sign(r3).*(exp(abs(r3)) - exp(1));
custpts = CustomStartPointSet([r1,r2,r3]);

以下是该算法的变体。通过下界方法生成一个介于 0 和无穷大之间的数字。使用该数字作为点的半径。通过对每个分量取随机数并乘以半径来生成该点的其他分量。您可以在乘以半径之前对随机数进行标准化，因此它们的范数为 1。有关此方法的实际示例，请参阅没有边界且起点分布广泛的 MultiStart。

示例：寻找更好的解

MultiStart 无法在寻找全局或多个局部最小值中找到全局最小值。有两种简单的方法可以寻找更好的解：

使用更多起点
给搜索空间设定更严格的边界

设置问题结构体和 MultiStart 对象：

problem = createOptimProblem('fminunc',...
    'objective',@(x)sawtoothxy(x(1),x(2)),...
    'x0',[100,-50],'options',...
    optimoptions(@fminunc,'Algorithm','quasi-newton'));
ms = MultiStart;

使用更多起点

对问题运行 MultiStart，得到 200 个起点，而不是 50 个：

rng(14,'twister') % for reproducibility
[x,fval,exitflag,output,manymins] = run(ms,problem,200)

MultiStart completed some of the runs from the start points.

53 out of 200 local solver runs converged with a positive local solver exit flag.

x =

   1.0e-06 *

   -0.2284   -0.5567


fval =

   2.1382e-12


exitflag =

     2


output = 

  struct with fields:

                funcCount: 32670
         localSolverTotal: 200
       localSolverSuccess: 53
    localSolverIncomplete: 147
    localSolverNoSolution: 0
                  message: 'MultiStart completed some of the runs from the start points.↵↵53 out of 200 local solver runs converged with a positive local solver exit flag.'

manymins = 
  1x53 GlobalOptimSolution

  Properties:
    X
    Fval
    Exitflag
    Output
    X0

这次 MultiStart 找到了全局最小值，并找到了 51 个局部极小值。

要查看局部解的范围，请输入 histogram([manymins.Fval],10)。

更加严格的起点约束

假设您认为有趣的局部解的所有分量的绝对值都小于 100。起点边界的默认值为 1000。要使用不同的边界值，请生成一个 RandomStartPointSet，并将 ArtificialBound 属性设置为 100：

startpts = RandomStartPointSet('ArtificialBound',100,...
    'NumStartPoints',50);
[x,fval,exitflag,output,manymins] = run(ms,problem,startpts)

MultiStart completed some of the runs from the start points.

29 out of 50 local solver runs converged with a positive local solver exit flag.

x =

   1.0e-08 *

    0.9725   -0.6198


fval =

   1.4955e-15


exitflag =

     2


output = 

  struct with fields:

                funcCount: 7431
         localSolverTotal: 50
       localSolverSuccess: 29
    localSolverIncomplete: 21
    localSolverNoSolution: 0
                  message: 'MultiStart completed some of the runs from the start points.↵↵29 out of 50 local solver runs converged with a positive local solver exit flag.'

manymins = 
  1x25 GlobalOptimSolution

  Properties:
    X
    Fval
    Exitflag
    Output
    X0

MultiStart 找到了全局最小值，并找到了 22 个不同的局部解。要查看局部解的范围，请输入 histogram([manymins.Fval],10)。

与在使用更多起点中发现的极小值相比，本次运行发现了更好（更小）的极小值，并且成功运行的百分比更高。