一类非单调线搜索的拟牛顿法和共轭梯度法研究

论文摘要

本文研究了一类非单调线搜索技术在无约束优化问题拟牛顿算法和共轭梯度算法中的应用．该类非单调线性搜索是属于Armijo型的线性搜索，其思想来源是戴彧虹2002年提出的一类单调线搜索，他那里是和共轭梯度算法结合进行研究的．本文研究的这类非单调线搜索减弱了搜索终止条件，并且在每步计算步长因子αk时，引进适时变化的初始测试步长rk，而不是沿用最初提出的非单调Grippo-Lampariello-Lucidi搜索中的固定的初始测试步长α．如果初始测试步长的选取与梯度无关，那么本文研究的非单调线性搜索实质上是一类不带导数的线性搜索．它的单调情形，曾由Leone、Gaudioso和Grippo研究过，但那里仅就一类特殊的初始测试步长做了讨论；本文这里所做的收敛性研究并不依赖于初始测试步长．第一章前三节简要描述了拟牛顿法和共轭梯度法的原理、发展和研究动态．第四节，简介了非单调线搜索技术，列举出典型形式，其中有些是近年来的新结果．第五节简述了本文的创新点．第二章研究一类非单调线搜索在拟牛顿算法中的应用．众所周知，BFGS校正公式是数值表现最好的拟牛顿算法之一，本章在不对BFGS公式做任何修改的情况下，使其与一类非单调线搜索结合，证明了全局收敛性．一般地，非单调线搜索方法的全局收敛性证明常常需要满足：（1）充分下降条件：gkTdk≤-c1‖gk‖2，（2）有界性条件：‖dk‖≤c2‖gk‖，其中c1和c2是正数．这两个条件较强，一般的拟牛顿法难以满足．这也正是本问题研究难点．本文的一般性假设与文献[25]相同，比文献[69]有所减弱，特别是去掉了文献[63]所要求的搜索方向dk满足充分下降条件以及有界性条件的假设．数值结果表明了算法的有效性．第三章研究一类非单调线搜索在共轭梯度算法中的应用．目前比较多的共轭梯度算法研究是采用Wolfe单调线搜索进行的，通过构造Zoutendijk条件，利用反证法证明收敛性．这里研究的是一类Armijo型非单调线搜索共轭梯度算法的全局收敛性，证明思路没有采用上述方式．我们研究了非单调线搜索在四种共轭梯度算法中的收敛性情况．对于一般非凸函数，证明了这类非单调线搜索下修正的PRP方法的全局收敛性．在适当增加条件时，对一般非凸函数，证明了这类非单调线搜索下修正的DY方法、HZ方法和修正的FR方法的全局收敛性．通过数值结果比较了四种算法的优劣．本文有如下创新点：（1）研究了一类线性搜索，数值结果表明，无论是单调搜索还是非单调搜索，它优于传统的Grippo-Lampariello-Lucidi搜索。（2）对非单调线性搜索的研究，不依赖于充分下降条件和有界性条件。（3）在一类非单调线性搜索下，证明了BFGS法和四种共轭梯度算法的全局收敛性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 线性搜索准则
• 1.2 拟牛顿算法
• 1.3 共轭梯度算法
• 1.4 非单调线搜索技术
• 1.5 本文创新点
• 2 一类非单调线搜索拟牛顿算法
• 2.1 引言
• 2.2 算法
• 2.3 算法的收敛性分析
• 2.4 数值结果
• 3 一类非单调线搜索共轭梯度算法
• 3.1 引言
• 3.2 算法
• 3.3 算法的收敛性分析
• 3.4 数值结果
• 参考文献
• 攻读硕士学位期间论文撰写、发表情况
• 致谢