非约束优化的介绍

Wolfram 语言收集了大量的命令来进行非约束最优化(FindMinimumFindMaximum),求解非线性方程(FindRoot) 及非线性拟合问题 (FindFit). 一般来说,所有这些函数都从一些初始值开始搜索,然后采取减少(或者对于 FindMaximum 来说,增加) 一个目标或者优质函数的步骤.

FindMaximum 的搜索过程在某种程度上类似于在浓雾天气中力图到达山峰的登山者; 在任何给定点,基本上登山者所知道的有他们的位置,斜坡的陡峭程度,以及下降线的方向. 一种办法是永远向上走. 只要登山者沿足够的陡峭度上山,他们最终将达到一个高峰,虽然这可能不是最高的一个山峰. 同样地,在搜索一个极大值的过程中,绝大部分方法都是上升法,即在每个步骤中都增加高度并且在到达任何峰值的时候停止,不管它是不是最高峰.     

对于寻找局部极小值,我们可以把它考虑为一个类似于爬山过程的逆转过程,即考虑下降方法. 在大多数情况下,优化方面的文献都考虑寻找极小值的问题,而且因为这对于绝大多数 Wolfram 语言命令都适用,从现在开始,我们的这篇文档将遵从这个惯例.

例如,函数 没有下界,因而它没有全局极小值,但是它有无限多的局部极小值.

这里加载一个包含一些功用函数的封装包.     
In[1]:=
Click for copyable input
下面是函数 x Sin[x+1] 的图示.
In[2]:=
Click for copyable input
Out[2]=
这里显示了 FindMinimum 对函数 x Sin[x+1] 所采取的步骤,起始点为 .
In[3]:=
Click for copyable input
Out[3]=

命令在由这个notebook自动加载的Optimization`UnconstrainedProblems`包里有定义. 它运行 FindMinimum,跟踪函数和梯度的计算以及在搜索过程中采取的步骤 (利用 EvaluationMonitorStepMonitor 选项),并且把它们在函数的图示上显示出来. 步骤采用蓝线表示,函数的计算用绿点表示,而梯度计算用红点表示. 所找到的极小值用一个大黑点表示. 从图示中,我们可以清楚地看到 FindMinimum 已经找到一个局部极小点.     

这里显示了 FindMinimum 对函数 x Sin[x+1] 所采取的步骤,起始点为 .     
In[4]:=
Click for copyable input
Out[4]=

从 2 开始,FindMinimum 走向不同的局部极小值,那里的函数值小于第一次找到的极小值.     

从这两个图示,您可能会得出这样的结论: 如果您起始于一个点,在该点函数是向下倾斜的,那么沿着这个方向您将总是朝着下一个极小值前进. 然而,实际情况并非总是如此;FindMinimum 所采取的步骤通常是由函数值和其导数值确定的,因此,如果导数相当小,FindMinimum 可能会认为它需要经过相当长的时间才能找到极小值点.    

这里显示了 FindMinimum 对函数x Sin[x+1] 所采取的步骤,起始点为 .
In[5]:=
Click for copyable input
Out[5]=

接近一个局部极大值,以该点为起始点,第一个步骤相当大,因此 FindMinimum 返回一个完全不同的局部极小值.

所有这些命令的名字里都有 "find" 这个词,这是因为一般而言,其设计就是为了搜寻任何满足期待条件的点. 所找到的点可能不是唯一的 (在寻找根的情况下) 或者甚至不是最好的(在拟合,寻找极小点或者极大点的情况下),或者正如您所看到的,甚至不是最接近初始条件的点. 换句话说,我们的目的是找到任何点,在该点有一个根,或者一个局部极大值或者极小值. 相比之下,函数NMinimize 努力寻找函数的全局极小值,但是 NMinimize 通常也可以通过约束条件来界定问题的区域. 但是,这种普遍性是需要付出代价的NMinimize 必须做更多的工作,而且事实上,它可能需要在过程的最后调用一个 函数来修饰或完善我们所得到的结果,所以一般来说它需要花比 函数更长的时间.     

在二维空间,极小化问题就更为复杂,因为我们需要确定步骤的方向和步长.

这里显示了 FindMinimum 寻找函数 的局部极小值所采取的步骤,起始点为 .
In[6]:=
Click for copyable input
Out[6]=

对于二维空间的 命令与一维的情况类似,但是它在函数的等值线图上叠加地显示了步骤和求值计算. 在这个例子中,很明显 FindMinimum 需要几次改变方向以到达局部极小值. 您可能会注意到第一个步骤是沿最速下降方向 (即垂直于等值线或平行于梯度)开始的. 最速下降法确实是一个寻找局部极小值的可能策略,但是它往往收敛速度不快. 在这个例子的随后步骤里,您可能会注意到搜索方向不完全垂直于等值线. 搜索过程使用了过去的步骤所得到的信息,以图得到有关函数曲率的信息,这样通常可以给它一个更好的搜寻方向. 另一个策略是使用函数的二阶导数,通常它的收敛速度更快,但也更加昂贵. 我们通常称之为"牛顿"方法.

这里显示了使用牛顿方法时所采取的步骤.
In[7]:=
Click for copyable input
Out[7]=

在这个例子中,可以清楚地看到,牛顿 方法所使用的有关函数曲率的额外信息,对获得极小值所需步骤数带来很大差别. 尽管牛顿方法需要较少的步骤,它有可能会需要更多的执行时间,因为它需要符号式地计算一次Hessian,然后在每个步骤对它进行数值计算.     

通常我们需要权衡收敛速度或所采取的步骤总数和每个步骤的代价. 根据您所要解决的问题的大小,您可能想要选择一个特殊的方法,以找到最符合这一特殊问题的折衷条件. 这个文档的目的是帮助您理解这些选择,以及如何从 Wolfram 语言的函数里获得最好的结果的一些方法. 在大多数情况下,我们将使用一些例子来说明想法,但是我们也将提供这个方法背后的数学理论的一些有限的论述,这样您就可以更好地了解这些例子是如何工作的.

在大多数情况下,函数 的局部极小化方法是基于如下一个二次模型

下标 指的是第 次迭代步骤. 在牛顿方法中,该模型是基于准确的Hessian矩阵 的,但是其他的方法使用 的近似,这样通常计算起来不太昂贵. 通常我们计算一个试验步骤 作为模型的极小化子(minimizer),它还满足了线性方程组.     

如果 足够平滑而且 足够接近一个局部极小值,那么通过 ,步骤序列 保证收敛到局部极小值. 然而,在一个典型的搜索中,初始值很少能足够接近到可以产生理想的收敛性的程度. 此外, 往往是实际 Hessian 的一个近似,并且在开始搜索的时候,近似往往是相当不准确的. 因此,我们有必要对步骤序列提供额外控制,以改善收敛的机会和收敛速度. 这里有两种常用的控制步骤的方法: 线搜索和信赖域方法.

线搜索方法 方法中,对于每个找到的试验步骤 ,沿着 方向要进行一个一维搜索以使得 . 您可以选择 使其在该方向极小化 ,但是这样做是多余的,在要求 在值和斜率上显著下降的条件下,对于 的适当近似,收敛性是可以被证明的. Wolfram 语言就使用这些条件形式,我们称之为 Wolfe 条件.

信赖域方法 方法中,有一个半径 ,在该半径内,方程 (1) 中二次模型 信赖 为适当地代表了原函数. 然后,信赖域方法试图寻找(1)在约束条件 下的极小值,而不是求解 (1) 的非约束极小值. 如果 足够接近一个极小值并且我们的模型是好的,那么极小值往往位于这个圆内,并且收敛相当迅速. 然而,在搜索开始不久的时候,极小值将位于边界上,此时会有一些找到该约束问题的近似解的方法. 一旦找到近似解,我们把函数值的实际减少量与函数值的预测减少量相比,然后根据实际值与预测值的接近程度,对 进行调整.

对于一个单变量平滑函数的符号化极小化,所有要做的不过是寻找一个点,使得导数为零而二阶导数为正数. 在多维空间里这意味着梯度为零而Hessian必须是正定的. (如果 Hessian 是半正定的,该点是一个极小化点,但不一定是严格的). 在一个数值算法的收敛过程中,我们必须要追踪收敛性情况并判断什么时候极小值近似已足够好. 这是以所采取的步骤系列和在这些点的函数值,函数的梯度,以及有可能是这些点上的Hessian为基础的. 通常,如果 Wolfram 语言的 函数不能相当肯定这个判断是准确,它们会发出一个提示. 但是,记住,不连续的函数或者尺度迅速变化的函数可以愚弄任何数值算法.

求解 非线性方程组求解 时,会出现许多和寻找一个 局部极小值 相同的问题. 事实上,通过考虑一个所谓的优值函数,即在方程的根处的值为零的函数,我们有可能使用许多和极小化相同的技术,而且还有一个优点,就是已知函数的极小值为0. 使用这种方法也不总是有利的,我们有一些专门为非线性方程设计的方法.

我们演示的大部分例子将来自一维或二维空间. 这绝不是因为 Wolfram 语言只能限制于计算这样小的例子,而是因为使用这样的例子很容易直观地演示理论和方法背后的主要原理.