Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

局部最优与全局最优

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

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

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

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

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

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

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

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

搜索更小的最小值

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

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

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

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

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

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

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

吸引盆

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

ddtx(t)=f(x(t)),

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

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

一维盆

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

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

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

多个吸引盆

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

y ≥ |x|

y ≥ 5 – 4(x–2)2

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

 用于生成图窗的代码

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

相关主题