非约束最优化：步控制介绍

介绍信赖域方法
线搜索方法

介绍

即使是局部模型以实际的 Hessian 为基础的牛顿法，除非已经接近根或者极小值，否则模型的步骤可能不会使您更接近解. 下面的问题，就是一个简单的例子.

这里下载一个包含一些功用函数的程序包：
这里给出一个不使用步控制进行根搜索的简单例子，其中迭代在两个点之间交替进行而不收敛. 注: 在某些平台上，您可能会看到收敛. 这是因为在机器数算术上的轻微变动，就可能足以打破这种振荡.    
下面给出启用步控制的相同例子. 由于第一个计算点没有降低函数的大小，线搜索对步骤进行了限制，因此迭代最终收敛到解：

一个良好的步控制算法可以避免出现重复的情况或从接近根或极小值附近的区域远离的情况. 然而与此同时，当基于模型函数的步骤适当时，步长控制算法不应对它们进行限制，否则，算法的收敛速度将受影响. 两个常用的步长控制算法是线搜索和信赖域方法. 在一个线搜索方法中，模型函数给出一个步骤方向，然后沿着这个方向搜索以找到一个可以达到收敛的适当的点. 在信赖域方法中，每一步要更新一个距离，而在这个距离内模型函数是被信任的. 如果模型步骤位于该距离之内，则可以被使用；否则，模型函数在信赖域边界上的极小值将被使用. 一般来说，信赖域方法更稳健，但是它们需要更多的数值线性代数运算.

这两个步控制方法在原先是在考虑极小化问题时发展出来的. 然而，当与优值函数一起使用时，它们也能够很好地运用于非线性函数的求根运算. 在 Wolfram 语言中，使用的是2-范数优值函数 .

线搜索方法

像牛顿法这样的方法要选择一个步，但是该步的有效性只限于函数的牛顿二次模型真实体现函数的情况. 线搜索方法的基本思想是使用所选步的方向，但要通过求解一个极小化

的一维问题控制步长. 这里 是从位置 选择的搜索方向. 请注意

所以，如果您能够计算梯度，那么您实际上可以使用导数进行一个一维搜索.

通常，一个有效的线搜索只选取 方向，因为一个合理的方法应该保证搜索方向是一个下降的方向，这可以表示为 .

通常不值得花费精力去寻找 的精确极小值，因为搜索方向很少恰好是正确的方向. 通常只要能靠近就足够了.

测量进度的一个条件被称为对于一个候选值 的 Armijo 条件或充分下降条件.

往往在这种情况下，方法将会收敛，但是对于有些方法，光有 Armijo 并不保证光滑函数的收敛性. 加上曲率条件，

可以证明许多方法对于光滑函数是收敛的. 所有这些条件合起来被称为强Wolfe条件. 您可以使用 "LineSearch" 的"DecreaseFactor"->μ 和 "CurvatureFactor"->η 选项控制参数 和 .

"CurvatureFactor"->η 的默认值是 ，除了 Method->"ConjugateGradient" 的情况，这时候使用 ，因为算法通常对接近精确的线搜索表现得更好. 越小，线搜索越接近精确.

如果您看一下表示在两个维度方向上迭代搜索的图表，您可以看到计算是沿着线搜索的方向分散开来. 通常情况下，只需要几个迭代过程就能找到满足条件的一个点. 然而，线搜索并不总是能够找到符合条件的一个点. 通常这是因为没有足够的精确度来计算足够接近以满足条件的点，但是它也可能由于函数并不完全光滑或者在一个极小值附近变化极慢引起的.

这里加载一个包含一些功用函数的程序包：

这样就出现了问题，因为函数真正的不同与在点周围的计算的不同相比，是可以忽略不计的，这从我们所画的图可以看出.

有时候，减去常量可能会有帮助，这样函数中微小的改变都会比较明显.

然而，在这种情况下，近似值只是稍微地更接近了我们的目标，因为从图示中可以看出，函数在接近0的时候噪声太大.

因此，要更加接近零点的正确值，我们需要更高的精确度来更准确地计算函数.

对于一些问题，特别是当您从远离根或者局部极小值起始搜索的时候，我们可能最好能够限制步骤. 使用线搜索方法，我们可以使用 "MaxRelativeStepSize" 方法选项来做到这一点. 对此我们所选择的默认值旨在避免搜索失去控制，但同时也不阻止搜索过程使用合理的大步骤，如果是适当的话.

在下面的这个例子中，牛顿步是非常大的，因为起始点在一个雅可比（导数）接近奇异的位置. 步长（并不严格地） 受选项所限制：
下面是同样的例子，但是这里我们使用了更严格的步长限制，根在接近初始条件的位置找到：

请注意，您需要小心，不要把 "MaxRelativeStepSize" 选项设置得太小，否则将影响收敛性，特别是当极小值和根接近零时.

下表总结了各种选项，我们可以使用它们来控制线搜索.

选项名
默认值
"Method"Automatic用来执行线搜索的方法； 可以是 Automatic，"MoreThuente"，"Backtracking"，或者是 "Brent"
"CurvatureFactor"AutomaticWolfe 条件中的因子 ，位于 0 和 1之间； 较小的 产生一个更为精确的线搜索
"DecreaseFactor"1/10000Wolfe条件中的因子 ，位于 0 和 之间
"MaxRelativeStepSize"10相对于当前搜索点的范数，将要采取的最大的步长, 可以是任何正数或者，对于没有限制的情况，可以是

"StepControl"->"LineSearch" 的方法选项.

以下各节我们将介绍在 Wolfram 语言中执行的三种线搜索算法. 我们将使用 Rosenbrock 函数进行比较.

这里使用无约束问题的程序包来建立经典 Rosenbrock 函数，它有狭窄弯曲的谷部：

MoreThuente

FindMinimum、FindMaximum 和 FindFit 所使用的默认线搜索采用 More 和 Thuente 在 [MT94] 中描述的方法. 它试图使用包围以及二次和三次插值找到满足下降条件和曲率条件的一个点.    

下图显示了使用默认线搜索参数的牛顿方法的步骤和函数求值计算. 只有红色和绿色的点表示在线搜索中这些地方的函数和梯度被计算了，但并不满足 Wolfe 条件，所以没有采取步骤：

那些只计算了函数和梯度的点是那些在线搜索阶段尝试过，但并没有满足这两个条件的点. 除非受 "MaxRelativeStepSize" 限制，线搜索总是从完整步长起始（），这样如果该完整的步骤（在这种情况下为牛顿步）满足线搜索标准，它就将被采用，以确保在接近极小值时的充分收敛速度.

降低曲率因子，也就是说线搜索在更接近精确极小值处结束，会降低牛顿法所采取的步骤数目，但是增加了函数和梯度计算的总次数.

这里显示了牛顿法所用的步骤和计算，其中线搜索参数中的曲率因子比默认值小. 只有红色和绿色的点表示在线搜索中这些地方的函数和梯度被计算了，但并不满足 Wolfe 条件，所以没有采取步骤：

这个例子表明了为什么一个更精确的线搜索不一定是更好的. 当线搜索采取的步骤到达狭谷的底部右侧，牛顿步沿着谷的方向移动，而没有看到其曲率（谷的曲率超过二次），结果是牛顿步变得太长，虽然方向是更好了. 另一方面，一些方法，比如共轭梯度法，需要有一个更好的线搜索方法，以改善收敛性能.

回溯

这是一个简单的线搜索方法，它从给定的步长开始，回溯到长度为0的步长，当充分下降条件得到满足的时候停止. 一般来说，只采用回溯，也不能保证您可以满足曲率条件，即使对于很友好的函数，亦是如此，因此方法的收敛性没法得到保障. 然而，回溯线搜索也并不需要在每个点对梯度进行计算，因此，如果梯度计算代价相对较高，这可能是一个不错的选择. 在 FindRoot 中，它被用来作为默认的线搜索方法，因为计算优值函数的梯度包括对雅可比的计算，所以代价相对较高.

每个回溯步骤的执行都进行了多项式插值和对插值寻找极小值点. 这个点 ，只要它位于 和 之间，就会被使用，这里 是参数 α 的前一个值，并且 . 默认情况下， 并且 ，但是它们可以通过方法选项 "BacktrackFactors"->{c1,c2} 控制. 如果您赋予这些因子单一的值，这就设置了 ，并不再使用插值. 值 1/2 产生二分法.

在这个例子中，相对比较大的回溯因子的影响是显而易见的：
选项名
默认值
"BacktrackFactors"{1/10, 1/2}决定在回溯步骤间，尝试步长所必须缩小的最小和最大因子

线搜索 Method->"Backtracking" 的方法选项.

布伦特

这是对线搜索使用布伦特 [Br02] 的无导数单变量方法. 它试图在容差范围内寻找到 的极小值，不论下降因子和曲率因子的大小. 实际上，它分两个阶段进行. 首先，它试图包围根，然后它使用布伦特的插值/黄金分割结合方法寻找极小值. 这种线搜索的优点是它并不需要像其他两种方法所要求的步必须在一个下降的方向，因为它会在两个方向上查找，以试图包围极小值. 因此，它对于不用导数的主轴方法非常合适. 这种线搜索方法的缺点是它通常使用许多函数计算，因此它比其他两种方法效率更低.

这个例子显示了对于线搜索使用布伦特方法的效果. 请注意，在包围根的阶段，它可能会使用负的 值. 虽然在这个例子中，牛顿步的数目相对较少，函数计算的数目远远大于其他线搜索方法：

信赖域方法

信赖域方法在当前搜索点附近具有一个区域，其中关于局部极小化的二次模型

被“信赖”为正确的，并且步骤被选择留在该区域内. 在搜索的过程中，区域大小根据模型和实际函数计算的符合程度被修改.

非常典型地，信赖域采取的是一个满足 的椭圆. 是一个对角缩放（通常采用近似 Hessian 的对角），而 是信赖域半径，它在每个步骤被更新.

当基于二次模型的步骤本身位于信赖域之内的时候，那么就认为函数值在变小，因而采用这一步骤. 因此，正如线搜索方法中一样，步控制不会干涉算法在二次模型表现良好的极小值附近的收敛效果. 当基于二次模型的步骤位于信赖域之外时，则采用一个只到边界位置的步骤，以使得该步骤成为二次模型在信赖域边界处的近似极小化步骤.

一旦一个步骤 被选择，该函数就在新的点被计算，而实际函数值与通过二次模型预测所得到的值互相对照. 真正计算的是实际与预测减少量的比率.

如果 接近 1，那么该二次模型是一个相当不错的预测器，该区域的大小可以扩大. 另一方面，如果 太小，则该区域的大小就要被降低. 当 低于某一阈值 时，该步骤被拒绝并重新计算. 您可以使用方法选项"AcceptableStepRatio"->η 控制这一阈值. 通常情况下， 是相当小的，以避免走向极小值的步骤也被拒绝. 然而，如果在一个点获取二次模型相当昂贵（例如，计算 Hessian 需要花费相对较长的时间），一个较大值的 将降低 Hessian 计算的次数，但是它可能增加函数计算的次数.

要开始信赖域算法，需要确定一个初始半径 . 默认情况下，Wolfram 语言使用基于受比较宽松的相对步长限制的模型(1) 的步骤的大小. 然而，在某些情况下，这可能使您离开您原来感兴趣的区域，所以您可以使用选项 "StartingScaledStepSize"->Δ0 指定一个初始半径 . 该选项在它的名字中包含 Scaled，因为信赖域半径使用了对角缩放 ，所以这不是一个绝对的步长.

这里加载一个包含一些功用函数的程序包：
这里显示在搜索一个与 Rosenbrock 函数类似的函数的局部极小值的过程中，所采用的步骤和计算，用的是了利用信赖域步控制的牛顿法：

该图示看起来很糟糕，因为搜索在如此大的区域上延伸，以致函数的精细结构不能在这样的尺度上真正看到.

这里显示了对同样函数的步骤和计算，但这里有一个限制了的初始信赖域半径 . 这里，搜索更接近初始条件，并且沿着狭谷进行：

我们还可以使用选项 "MaxScaledStepSize"->Δmax 对信赖域半径设置一个整体上限，使得对任何步，Δk≤Δmax.

由于在函数计算中数值舍入的问题，信赖域方法也可能在不够光滑的函数上遇到困难. 当函数不足够平滑的时候，信赖域的半径将持续减少. 最终，它将达到一个实际上值为零的点.

这里从 Optimization`UnconstrainedProblems` 程序包中以一种可以被 FindMinimum 求解的形式获得Freudenstein-Roth测试问题. （参见 "测试问题".）
这里使用默认方法对函数寻找一个局部极小值. 在这种情况下的默认方法是（信赖域）Levenberg-Marquardt 方法，因为函数是一个平方和的形式：

出现的提示信息表明，相对于搜索点的大小，信赖域的大小实际上已经变为零，所以所采取的步骤将效果甚微. 注：在某些平台上，由于机器运算的微小差异，该信息可能不会显示. 这是因为产生该信息的原因与数值的不确定性有关，这在不同的平台上可能产生不同的变化.

这里在最后找到的点沿着 方向画出变差函数图：

沿着一个方向的图使我们相当清楚为什么进一步的改进是不可能的. 在这种情况下 Levenberg-Marquardt 方法陷入困境的部分原因是收敛相对缓慢，因为残差在极小值处非零. 使用牛顿方法，收敛速度更快，完整的二次模型可以更好地估计步长，因此 FindMinimum 可以对默认容差得到满足更有信心.

下表总结了对于信赖域步骤控制的选项.     

选项名
默认值
"AcceptableStepRatio"1/10000阈值 ，使得当实际与预测减少量的比率 时，搜索移动到已计算的步骤
"MaxScaledStepSize"∞值 ，使得对于所有步骤，信赖域大小
"StartingScaledStepSize"Automatic初始信赖域大小

"StepControl"->"TrustRegion" 的方法选项.