《线搜索准则分析综述》2300字

线搜索准则分析综述在完成下降方向的确定后，需要通过线搜索过程以选取步长。线搜索方法设计的优劣在很大程度上会对算法的性能产生直接影响。可以设想，最为理想的线搜索结果应是选取出能够使下一迭代值在既定的下降方向上最小化的步长，即可表示为：α实现了上述思想的算法被称为精确线搜索方法。尽管能达到最速下降的理想目的，但它在每次迭代时均须完成一次最小值问题的求解，这将带来及其繁重的计算量进而大大提升了问题的计算难度，在实际计算中很少被采用。也正因此非精确线搜索的研究受到了优化学者们广泛的重视与讨论。常用的非精确线搜索规则有如下几种：Armijo线搜索准则：引入参数δ,σ∈0,1,s>0。令αk=sσℎ fxk+Wolfe线搜索准则：引入参数0<δ<σ<1。选择 fxGoldstein线搜索准则：引入参数σ∈(0,1/2)。选择能够满足式（1.2.3）的 σ≤fx上述列举的三类非精确线搜索准则在产生迭代步长时，均会受到常数参数σ,δ,s的影响，因此在实际应用时需要对参数选择进行审慎的考虑。以上三种线搜索准则具有一个共同特性，其产生的迭代值是单调下降的，即满足：f因此我们称这样的线搜索方法为单调线搜索方法。尽管它们能在局部迭代时获得令人满意的下降，但在处理某些目标函数非线性程度较高，在可行域中存在狭长的弯曲谷底的无约束优化问题时，这种目标函数的迭代值严格下降的性质将会极大地降低搜索算法的收敛速度——一旦函数迭代进入了狭长的弯曲峡谷，就只能被迫沿着谷底缓慢前进。在此过程中相邻迭代点之间的前进距离将极为微小，甚至可能出现锯齿现象使得算法陷入低效困境中。为了解决此类单调线搜索方法的局限性，Grippo、Lampariello和Lucidi在1986年首次提出了非单调线搜索方法。非单调线搜索方法的核心思想在于它并不要求迭代过程中产生的迭代值始终下降，而是在保证算法的全局收敛性的前提下，通过给出一些更为宽容的迭代条件，以期提高找到最优解的可能性及算法收敛速率。在某些应用单调线搜索方法会出现迭代点被迫沿着狭长谷底缓慢爬行情形的问题中，它可以有效地提高算法的收敛速度，避免无意义的重复迭代。数值试验的结果表明非单调线搜索方法在解决一些困难的非线性问题时能够表现出良好的数值效果，也正因此成为了数值优化领域经久不衰的研究热点之一。Grippo、Lampariello和Lucidi以Armijo线搜索方法为基础，在此之上实施改良，最早提出了一类关于牛顿法的非单调线搜索方法框架。该方法可以概述为：引入参数λ1,λ2,σ,δ，满足0<λ1<λ2<1fxk+其中，gk是目标函数在第k次迭代点xk处的梯度，“内存”mk显然当M=0时，该非单调线搜索方法将退化为Armijo线搜索方法。Grippo、Lampariello和Lucidi在此后的研究中进一步证明，当目标函数存在下界且下降方向ppkT嵌入了该非单调框架的牛顿类算法具有全局收敛性。式（1.2.4）中引入的最大值函数使得下一迭代点的选择与生成将不再仅依赖上一相邻迭代点，而是由内存中相邻一组迭代点共同决定。该设计旨在增强算法的全局性，能够避免陷入迭代过程在局部徘徊不前的困境，显著提高了算法收敛速度。此后众多学者展开了对于该非单调线搜索框架的研究，试图将其与各类不同的优化算法相整合以期提高算法的整体性能，并对其在不同条件下的收敛性质进行了更为深入、广泛的探讨。例如，Zhou和Tits将该非单调线搜索框架延伸至极小化极大问题，并证明该框架能有效克服Maratos效应；Raydn首次实现其与Barazilai-Borwein梯度法的交叉结合，在较弱的条件下证明了该新型Barazilai-Borwein梯度法的全局收敛性；Birgin、Martinez和Raydan应用该非单调线搜索作为步长策略，对经典的投影梯度法做出更新与扩展。值得一提的是，他们创新性地设计出一种非单调线搜索步长策略与谱步长选择策略的结合方案，成功实现了收敛过程的加速。此外，对于该非单调线搜索框架本身的改良亦是学者们不懈努力的研究方向——Han和Liu提出了一种非单调Wolfe线搜索方法，并给出了在凸优化问题中，结合该框架的BFGS算法在一定条件下具有良好的全局收敛性的证明。该方法核心思想即在于用Wolfe线搜索准则替换框架中的Armijo准则，其步长需满足式（1.2.6）及（1.2.7）fx∇f其中δ∈(0,1)，σ∈(0,1/2)，p∈(−∞,1)尽管该非单调线搜索框架与多类优化方法的结合算法在众多数值案例中均表现出良好的计算性能，其仍然存在不可忽视的缺点。首先，最大值函数的引入使得过程中所产生的任一理想函数值在经历足够多次迭代后基本上都会被丢弃。其次，在某些情况下，该方法的数值性能十分依赖于固定上界M的选择。此外，Dai指出在目标函数f为一致凸