 |
线搜索方法
像牛顿法这样的方法要选择一个步，但是该步的有效性只限于函数的牛顿二次模型真实体现函数的情况. 线搜索方法的基本思想是使用所选步的方向，但要通过求解一个极小化
的一维问题控制步长. 这里 
是从位置 
选择的搜索方向. 请注意
所以，如果您能够计算梯度，那么您实际上可以使用导数进行一个一维搜索.
通常，一个有效的线搜索只选取 
方向，因为一个合理的方法应该保证搜索方向是一个下降的方向，这可以表示为 
.
通常不值得花费精力去寻找 
的精确极小值，因为搜索方向很少恰好是正确的方向. 通常只要能靠近就足够了.
测量进度的一个条件被称为对于一个候选值 
的 Armijo 条件或充分下降条件.
往往在这种情况下，方法将会收敛，但是对于有些方法，光有 Armijo 并不保证光滑函数的收敛性. 加上曲率条件，
可以证明许多方法对于光滑函数是收敛的. 所有这些条件合起来被称为强Wolfe条件. 您可以使用 
的"DecreaseFactor"->
和 "CurvatureFactor"->
选项控制参数 
和 
.
"CurvatureFactor"-> 的默认值是 
，除了 Method->"ConjugateGradient" 的情况，这时候使用 
，因为算法通常对接近精确的线搜索表现得更好. 
越小，线搜索越接近精确.
如果您看一下表示在两个维度方向上迭代搜索的图表，您可以看到计算是沿着线搜索的方向分散开来. 通常情况下，只需要几个迭代过程就能找到满足条件的一个点. 然而，线搜索并不总是能够找到符合条件的一个点. 通常这是因为没有足够的精确度来计算足够接近以满足条件的点，但是它也可能由于函数并不完全光滑或者在一个极小值附近变化极慢引起的.
| In[1]:= |
这样就出现了问题，因为函数真正的不同与在点周围的计算的不同相比，是可以忽略不计的，这从我们所画的图可以看出.
| In[24]:= |
| Out[24]= |  |
有时候，减去常量可能会有帮助，这样函数中微小的改变都会比较明显.
然而，在这种情况下，近似值只是稍微地更接近了我们的目标，因为从图示中可以看出，函数在接近0的时候噪声太大.
| In[19]:= |
| Out[19]= |  |
因此，要更加接近零点的正确值，我们需要更高的精确度来更准确地计算函数.
对于一些问题，特别是当您从远离根或者局部极小值起始搜索的时候，我们可能最好能够限制步骤. 使用线搜索方法，我们可以使用 
方法选项来做到这一点. 对此我们所选择的默认值旨在避免搜索失去控制，但同时也不阻止搜索过程使用合理的大步骤，如果是适当的话.
| In[3]:= |
| Out[3]= |  |
| In[4]:= |
| Out[4]= |  |
请注意，您必须小心，不要把 
选项设置得太小，否则将影响收敛性，特别是当极小值和根接近零时.
选项名 | 默认值 | |
| "Method" | Automatic | 用来执行线搜索的方法； 可以是 Automatic，  ， ，或者是  |
| "CurvatureFactor" | Automatic | Wolfe 条件中的因子  ，位于 0 和 1之间； 较小的  产生一个更为精确的线搜索 |
| "DecreaseFactor" | 1/10000 | Wolfe条件中的因子  ，位于 0 和  之间 |
| "MaxRelativeStepSize" | 10 | 相对于当前搜索点的范数，将要采取的最大的步长, 可以是任何正数或者，对于没有限制的情况，可以是  |
以下各节我们将介绍在 Mathematica 中执行的三种线搜索算法. 我们将使用Rosenbrock函数进行比较.
| In[5]:= |
| Out[5]= |  |
MoreThuente
FindMinimum、FindMaximum 和 FindFit 所使用的默认线搜索采用 More 和 Thuente 在 [MT94] 中描述的方法. 它试图使用包围以及二次和三次插值找到满足下降条件和曲率条件的一个点.
那些只计算了函数和梯度的点是那些在线搜索阶段尝试过，但并没有满足这两个条件的点. 除非受 
限制，线搜索总是从完整步长起始（
），这样如果该完整的步骤（在这种情况下为牛顿步）满足线搜索标准，它就将被采用，以确保在接近极小值时的充分收敛速度.
降低曲率因子，也就是说线搜索在更接近精确极小值处结束，会降低牛顿法所采取的步骤数目，但是增加了函数和梯度计算的总次数.
| In[31]:= |
| Out[31]= |  |
这个例子表明了为什么一个更精确的线搜索不一定是更好的. 当线搜索采取的步骤到达狭谷的底部右侧，牛顿步沿着谷的方向移动，而没有看到其曲率（谷的曲率超过二次），结果是牛顿步变得太长，虽然方向是更好了. 另一方面，一些方法，比如共轭梯度法，需要有一个更好的线搜索方法，以改善收敛性能.
回溯
这是一个简单的线搜索方法，它从给定的步长开始，回溯到长度为0的步长，当充分下降条件得到满足的时候停止. 一般来说，只采用回溯，也不能保证您可以满足曲率条件，即使对于很友好的函数，亦是如此，因此方法的收敛性没法得到保障. 然而，回溯线搜索也并不需要在每个点对梯度进行计算，因此，如果梯度计算代价相对较高，这可能是一个不错的选择. 在 FindRoot 中，它被用来作为默认的线搜索方法，因为计算优值函数的梯度包括对雅可比的计算，所以代价相对较高.
| In[32]:= |
| Out[32]= |  |
每个回溯步骤的执行都进行了多项式插值和对插值寻找极小值点. 这个点 
，只要它位于 
和 
之间，就会被使用，这里 
是参数 
的前一个值，并且 
. 默认情况下，
并且 
，但是它们可以通过方法选项 
控制. 如果您赋予这些因子单一的值，这就设置了 
，并不再使用插值. 值 1/2 产生二分法.
| In[33]:= |
| Out[33]= |  |
线搜索 Method->"Backtracking" 的方法选项.
布伦特
这是对线搜索使用布伦特 [Br02] 的无导数单变量方法. 它试图在容差范围内寻找到 
的极小值，不论下降因子和曲率因子的大小. 实际上，它分两个阶段进行. 首先，它试图包围根，然后它使用布伦特的插值/黄金分割结合方法寻找极小值. 这种线搜索的优点是它并不需要像其他两种方法所要求的步必须在一个下降的方向，因为它会在两个方向上查找，以试图包围极小值. 因此，它对于不用导数的主轴方法非常合适. 这种线搜索方法的缺点是它通常使用许多函数计算，因此它比其他两种方法效率更低.
| In[34]:= |
| Out[34]= |  |
