论文部分内容阅读
最优化方法是运筹学的一个重要组成部分,在自然科学、社会科学、生产实际、工程设计和现代化管理中具有广泛的应用.很多实际问题都可以归结为最优化的问题来解决,最优化问题的一个核心是设计有效的算法.最优化问题根据函数的具体性质和复杂程度,可以分为很多不同的类型。根据决策变量的取值是离散的还是连续的可以分为离散最优化和连续最优化。根据模型所有函数是否连续可微,可以分为光滑最优化和非光滑最优化。根据所有函数的变量是否为线性函数可分为线性最优化和非线性最优化。无约束优化问题是最优化问题的基础,通常采用迭代法求它的最优解.求解无约束优化问题的常用算法包括最速下降法、牛顿法、拟牛顿法、共轭梯度法等.最速下降法具有存储量小,结构简单,易于实现的优点,具有良好的全局收敛性,但最速下降法收敛速度很慢,理论上只具有线性的局部收敛速度.牛顿法因其局部收敛速度快等优点而受到广泛关注,并且它具有二阶收敛速度,这使得该算法应用很广泛.然而,牛顿法需要计算目标函数的二阶导数矩阵,当Hesse矩阵▽f2(xk)奇异时,牛顿方向可能不存在,或者存在但不是f(x)在xk处的下降方向.拟牛顿法克服了牛顿法的这一缺陷,它只需计算目标函数的一阶导数,而且大多数拟牛顿法是下降算法,具有良好的全局收敛性和超线性收敛速度.由于拟牛顿法的这一优点,使得该算法成为颇受欢迎的算法.但拟牛顿法在每次迭代过程中都需要存储一个矩阵,而且确定下降方向需要求解一个线性方程组,并且该方程组的系数矩阵一般是稠密的,所以该类算法不适合求解大规模问题.共轭梯度法很好的解决了最速下降法和牛顿法的缺点,它只需要利用一阶导数的信息,就可以避免牛顿法要计算Hesse矩阵并求逆的繁琐,也解决了最速下降法下降速度慢的缺陷,因此,这是一种很受广大研究者欢迎的方法,也是求解大型最优化问题最有效的问题之一。共轭梯度法最早是由Hestenes(?)口Stiefel于1952年在求解线性方程组时提出的,并由Fletcher和Reeves于1964年推广到非线性优化领域.随后,Beale, Powell, Fletcher等著名的优化专家对非线性共轭梯度法进行了深入研究,取得了十分丰富的成果.但几乎同时问世的拟牛顿方法由于其良好的计算表现以及快速的收敛性质很快受到了人们的青睐,从而在很长一段时间里共轭梯度法被研究者所忽视.近年来,随着计算机的飞速发展以及实际问题的需要,大规模优化问题越来越受到重视,而共轭梯度法正是求解大规模问题的一种主要方法.于是,共轭梯度法的理论研究又受到人们的关注.近年来,Nocedal、Gilbert、 Nazareth、storey、A-Baali、Dai、Yuan、Wang和Wei等中外学者对共轭梯度法继续不断地深入研究,在收敛性方面得到了不少新结果,使得共轭梯度法在理论和应用上的发展日趋进步。但由于各种决定步长因子大小的线搜索和搜索方向的不同组合,使得共轭梯度法仍然是一个非常值得研究的方向。在实际问题中,非线性共轭梯度法无论在科学、工程、经济和管理系统中,还是在政府决策、生产管理、交通运输和军事国防等方面都得到了广泛的应用.本文在共轭梯度法已有成果的基础上,对共轭梯度法进行了一些探讨,提出了几种新的共轭梯度法,并获得了一些收敛性结果.其主要内容如下:第一章介绍了无约束最优化问题的相关概念,以及几种常见的求解无约束最优化问题的方法,并介绍了本文的主要工作.第二章对近年来国内外备受关注的非线性共轭梯度算法研究的现状进行了总结和归纳.第三章在根据文献中βk得出一个新的βk的取值方法,结合文献中张秀军给出的一种新的线搜索构成一种新的方法,并给出充分下降性和收敛性的证明.第四章给出了一类求解无约束优化问题的共轭梯度法,在文献中提出的新的线搜索下给出了新算法的充分下降性和全局收敛性证明;本章第二节给出新的共轭梯度法充分下降性的证明,对共轭梯度法来说充分下降性是一个非常重要的性质,它对于保证算法的全局收敛性有很好的作用;第三节给出了这类新的共轭梯度法的全局收敛性证明.第五章根据文献得到一个新的βk的取值,并和文献中的一种新的线搜索方法结合成一种新的混合算法,并给出充分下降性和收敛性的证明.