非线性优化问题的一类新的混合共轭梯度算法研究

论文摘要

最优化是一门应用性很强的学科。随着计算机的发展以及实际问题的需要，大规模优化问题越来越受到重视。于是，快速有效的算法成为研究的热门方向。拟牛顿法和共轭梯度法就是两类比较成功的方法，本文主要研究共轭梯度法。1964年，Fletcher和Reeves提出了求解无约束极小化问题（?）f（x）的共轭梯度法，它是直接由Hestenes和Stiefel解线性方程组而独立提出的。共轭梯度算法由此开始发展。Powell在文献[5]给出了FR方法采用精确线性搜索时的收敛性证明。1985年，Al-Baali证明了FR方法在非精确线性搜索即强Wolfe线搜索下的全局收敛性。1969年，Polak，Ribiere和Polyak提出PRP方法，PRP方法和HS方法是目前认为数值表现较好的共轭梯度算法。但Powell在[5]中指出，即使采用精确线搜索，PRP方法也不具有全局收敛性。近年来，韩继业、袁亚湘、戴彧虹等许多学者在共轭梯度法的理论研究中取得了一批优秀的成果。1995年，Dai和Yuan提出了DY方法，并且证明了方法的全局收敛性。1996年，Dai和Yuan在[12]中对Wolfe线搜索进行了扩充，得到了广义Wolfe线搜索，并证明了广义Wolfe线搜索下FR方法的收敛性。1997年，L．Grippo和S．Lucidi提出了Grippo-Lucidi线搜索，并证明了在此搜索下Polak-Ribiere-Polyak方法的全局收敛性。1990年，Touati-Ahmed和Storey首先引入了混合共轭梯度算法，把βkFR和βkPR结合起来，得到具有较好的数值结果和全局收敛性的方法。Gilbert和Nocedal进一步研究了混合共轭梯度算法，并作了大量的数值实验。近年来出现许多新的确定参数βk的公式，李荣生在[16]中提出一种新的共轭梯度法，并在一般的非精确线性搜索条件下，证明了算法的全局收敛性，但其数值表现不尽如人意。本文对这种算法进行了改进，提出一种新的混合共轭梯度算法，并且在一般的非精确线搜索下，证明了其全局收敛性。通过数值试验表明新算法具有良好数值效果。论文整体安排如下：在第一章中，首先简要介绍非线性优化问题的主要理论，回顾了求解无约束优化问题常用的几类导数下降类算法。在第二章中，对一般共轭梯度法迭代格式，给出了一种新的公式，并且证明了此算法在采用Wolfe非精确线搜索下的全局收敛性，并采用文献[19]中的测试函数作了数值实验，新算法有较好的数值表现性。在第三章中，给出了一种推广的Wolfe线搜索，并且在第二章的基础上，证明算法的全局收敛性，最后用数值实验对在这种推广的Wolfe线搜索和Wolfe线搜索下数值表现作了比较。

论文目录

• 摘要
• Abstract
• 第一章:非线性优化问题简介
• §1.1 引言
• §1.2 非线性规划的最优化问题及最优性条件
• §1.3 无约束优化问题的导数下降类算法
• §1.4 本文的创新点
• 第二章:NCG-DY混合共轭梯度算法
• §2.1 引言
• §2.2 NCG-DY混合算法
• §2.3 数值实验
• 第三章:新的非精确线搜索下NCG-DY混合共轭梯度法
• §3.1 新的非精确线搜索下NCG-DY算法及全局收敛性
• §3.2 数值实验与分析
• 后记
• 参考文献
• 致谢