局部最优与全局最优

为什么求解器找不到最小的最小值

通常，求解器返回一个局部最小值（或最优值）。结果可能是全局最小值（或最优值），但无法保证如此。

• 函数的局部最小值是指这样的一个点：其函数值小于附近的点，但可能大于远处的点。

• 全局最小值是函数值小于所有其他可行点的点。

Optimization Toolbox™ 求解器通常会找到局部最小值。（此局部最小值可以是全局最小值。）这些求解器在吸引盆中找到起点的最小值。有关吸引盆的详细信息，请参阅吸引盆。

以下是此一般规则的例外情况。

• 线性规划问题和正定二次规划问题为凸问题，有凸可行区域，因此它们只有一个吸引盆。根据指定的选项，linprog 忽略用户提供的任何起点，quadprog 不需要起点，即使有时您可以通过提供起点来加快最小化的速度。

• Global Optimization Toolbox 函数，如 simulannealbnd，尝试搜索多个吸引盆。

搜索更小的最小值

如果需要全局最小值，您必须在全局最小值的吸引盆中为求解器找到一个初始值。

您可以通过以下方式设置初始值以搜索全局最小值：

• 使用初始点构成的规则网格。

• 如果所有问题坐标均为有界，则使用从均匀分布中抽取的随机点。如果某些分量为无界，则使用从正态分布、指数分布或其他随机分布中抽取的点。您对全局最小值的位置知道得越少，您的随机分布就应越分散。例如，正态分布很少对偏离均值超过三倍标准差的样本进行采样，但柯西分布（密度 1/(π(1 + x²))）会生成迥异的样本。

• 使用相同的初始点，并在每个坐标上添加随机扰动 - 有界、正态、指数或其他。

• 如果您有 Global Optimization Toolbox 许可证，请使用 GlobalSearch (Global Optimization Toolbox) 或 MultiStart (Global Optimization Toolbox) 求解器。这些求解器会自动生成在边界内的随机起点。

您对可能的初始点知道得越多，您的搜索就会越集中和成功。

吸引盆

如果目标函数 f(x) 是平滑的，则向量 –∇f(x) 指向 f(x) 下降最快的方向。最陡下降方程，即

$$\frac{d}{dt}x(t)=-\nabla f(x(t)),$$

会生成一条路径 x(t)，该路径随着 t 的增长而抵达局部最小值。通常，彼此靠近的初始值 x(0) 给出趋向于相同最小值点的最陡下降路径。最陡下降的吸引盆是导向相同局部最小值的一组初始值。

下图显示两个一维最小值。该图使用不同线型显示不同的吸引盆，并用箭头指示最陡下降的方向。对于此图以及后面的图，黑点表示局部最小值。从 x(0) 点开始，每条最陡下降路径都抵达包含 x(0) 的盆中的黑点。

一维盆

下图显示最陡下降路径在更多维度的情形中变得更为复杂。

显示来自不同起点的最陡下降路径的吸引盆

下图显示更加复杂的路径和吸引盆。

多个吸引盆

约束可以将一个吸引盆分成几个部分。例如，假设在以下约束条件下求 y 的最小值：

y ≥ |x|

y ≥ 5 – 4(x–2)².

下图显示两个具有最终点的吸引盆。

 用于生成图窗的代码

myabs = @(x) abs(x);
mycurve = @(x) 5 - 4.*(x-2).^2;
myline = @(x) max(myabs(x),mycurve(x));
mybrdr = @(x) 1 + heaviside(x-2);
myarea = @(x,y) heaviside(y - myline(x)).*mybrdr(x);
% myarea = 0 where infeasible, 1 when x < 2, 2 when x > 2
marinv = @(x,y) 1./myarea(x,y); % removes the infeasible region

plot(0,0,'k.','MarkerSize',25,'LineWidth',2);
hold on
grid on
plot(11/4,11/4,'k.','MarkerSize',25,'LineWidth',2);
fplot(mycurve,'k',[.9 3],'LineWidth',2)
fplot(myline,[-2 5],'k','LineWidth',2)
fsurf(marinv,[-2 5 -1,6],'EdgeColor','none','FaceAlpha',0.5)
colormap jet

在命令行中输入 plottools 以使用箭头绘制工具添加箭头。

最陡下降路径是向下一直延伸到约束边界的直线。从约束边界开始，最陡下降路径沿边界向下行进。最终点是 (0,0) 或 (11/4,11/4)，具体取决于初始 x 值是高于还是低于 2。

相关主题

• 改进结果