局部最优与全局最优 -凯发k8网页登录

局部最优与全局最优

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

curve with two dips; the lower dip is the global minimum, the higher dip is a local minimum

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

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

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

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

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

使用初始点构成的规则网格。
如果所有问题坐标均为有界，则使用从均匀分布中抽取的随机点。如果某些分量为无界，则使用从正态分布、指数分布或其他随机分布中抽取的点。您对全局最小值的位置知道得越少，您的随机分布就应越分散。例如，正态分布很少对偏离均值超过三倍标准差的样本进行采样，但 cauchy 分布（密度 1/(π(1 x²))）会生成迥异的样本。
使用相同的初始点，并在每个坐标上添加随机扰动 - 有界、正态、指数或其他。
如果您有 global optimization toolbox 许可证，请使用 (global optimization toolbox) 或 (global optimization toolbox) 求解器。这些求解器会自动生成在边界内的随机起点。

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

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

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

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

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

一维盆

curve with several dips. the bottom of each dip is a local minimum, and the region surrounding each local minimum is the basin of attraction.

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

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

two-dimensional region showing curved lines pointing to the minimum. each curve represents steepest descent flow.

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

多个吸引盆

two-dimensional region divided into differently-colored basins of attraction, with flow lines approaching the minimum in each region

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

y ≥ |x|

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

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

flow lines pointing to the two local minima. each colored region represents one basin of attraction.

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