Goldstein线搜索下的伪牛顿信赖域算法及其收敛性

摘要

对于非线性优化问题特别是无约束最优化问题，寻找其快速有效的求解方法一直是优化专家们研究的热门方向之一．其中线性搜索方法和信赖域算法是两大类非常重要的方法．这两类方法都有各自的优缺点，为了充分发挥这两类方法的优势，将这两类新方法相结合的思想逐渐发展产生了许多新的算法，其中大部分都具有良好的数值结果．本论文正是基于这种思想而提出了一种新的线性搜索方法和信赖域算法相结合的求解方法． 线性搜索方法一直是求解无约束优化问题的一类重要的算法，其中拟牛顿法是目前最成熟，应用最广泛的算法之一．自从第一个拟牛顿法DFP方法于1959年由Davidon提出，特别是Fletcher和Powell于1963年重新改写之后，对拟牛顿法的研究引起了广泛的重视，其收敛性问题的讨论也受到了人们的关注．拟牛顿法具有许多优点，比如：迭代中仅需一阶导数，不必计算Hesse矩阵，当H<,k<正定时，算法产生的方向均为下降方向，具有二次终止性等．在一定的条件下，文献[1，2，3，4，5]等给出了除DFP算法外的Broyden族算法的超线性收敛性，以及它具有n步二阶收敛速率的性质．拟牛顿法的缺点是所需存储量较大，对于大型问题，可能遇到存储方面的困难．随着对拟牛顿算法的深入研究，基于修正拟牛顿方程的一些非拟牛顿算法的研究也吸引了不少国内外学者．1991年，Ya-Xiang Yuan<'[6]>提出了一种修正的BFGS算法；1995年，Ya-Xiang Yuan、Richard.H.Byrd<'[7]>给出了一类非拟牛顿校正算法；同年赵云彬、易正俊<'[8]>提出了伪Newton-δ族算法，并证明了算法在Goldstein搜索下对一般目标函数的收敛性；1997年，陈兰平、焦宝聪<'[9]>教授在此基础上提出了一类新的非拟牛顿算法．这些算法中有些校正公式不满足拟牛顿方程，但同样具有二次终止性，矩阵的正定传递性，在精确和非精确线性搜索下的全局收敛性和超线性收敛性． 信赖域算法也是求解非线性优化问题的一类非常重要的数值计算方法，近些年来受到了非线性优化研究界非常的重视，一直是非线性优化的研究热点．其优点是它便于应用于大规模的具有稀疏Hesse矩阵的无约束问题和约束最优化方法中去．这是因为，当我们将拟牛顿法推广到稀疏无约束问题时，很难在保持稀疏性的前提下保证矩阵的正定性，而信赖域方法通过解一个带约束的优化子问题来代替线性搜索可以很好的解决这个问题． 与线性搜索方法相比，信赖域算法不仅具有很强的收敛性<'[10]>，而且对于病态问题也能有效地解决，需要的迭代次数少，但由于求解子问题花费代价高，往往不易求解新的迭代点，而线性搜索方法易于求得新的迭代点；为充分发挥两种方法的优势，1991年，Jorge Nocedal和袁亚湘<'[11]>提出将线性搜索方法和信赖域算法相结合来构造新计算方法的思想，在文[12]中，他们采用回溯(backtracking)线搜索，优点是不需重解子问题，大大减少了计算量，但为了保证序列{B<,k>}的正定性，却使得一些B<,k>未能满足拟牛顿方程，这样做往往使B<,k>逼近▽<'2>f(x<,k>)的效果不佳，从而信赖域子问题不能很好地逼近原问题．此外，1993年，邓乃扬等人<'[13]>首次提出了一类非单调的信赖域算法，并证明了此类算法的优越性．2004年，E.Michael Gertz<'[14]>提出了一种新的带线性搜索的信赖域方法，它不仅继承了文[12]中方法不需重解子问题的优点，而且由于在每步都采用Wolfe线搜索，使得序列{B<,k>}满足拟牛顿方程且保证其正定性，充分开发了拟牛顿校正公式的性质，克服了文[12]中方法的缺点． 基于对两种算法结合的考虑，本文提出了一种新的在Goldstein搜索下基于伪Newton-δ族校正公式的信赖域算法．此算法是基于非拟Newton方程，结合伪Newton-δ族算法给出的一种求解无约束非线性优化问题的新算法．由于赵云彬等已经证明了伪Newton-δ族算法在Goldstein搜索下对一般目标函数的收敛性，我们期望这种新的信赖域算法对一般目标函数有好的收敛性．数值实验表明，此类算法具有良好的计算效能和数值结果． 第一章我们简要介绍最优化问题的提出以及判断最优解常用的最优性条件，回顾无求解约束优化问题常用的几类算法． 第二章我们对Goldstein线搜索下的基于伪Newton-δ族校正公式的新信赖域算法的理论进行阐述，对其收敛性进行分析与证明，并进行适当的数值实验，以验证算法的有效性． 第三章我们提出了一类新的非拟牛顿非单调信赖域算法，该算法采用非单调Goldstein线搜索，基于非拟牛顿校正公式，是一种新的信赖域算法，同时我们证明了它的收敛性．

目录

文摘

英文文摘

首都师范大学学位论文原创性声明及授权使用声明

第一章非线性优化问题简介

1.1最优化问题的提出及最优性条件

1.2无约束优化问题的线搜索方法

1.3无约束优化问题的信赖域算法

1.4本文的创新点

第二章伪牛顿信赖域算法及其收敛性

2.1引言

2.2 Goldstein线搜索及其算法步骤

2.3信赖域子问题及伪Newton算法

2.4伪牛顿信赖域算法

2.5算法的收敛性

2.6数值试验

第三章一类非拟牛顿非单调信赖域算法

3.1信赖域子问题及非拟牛顿校正公式

3.2非拟牛顿非单调信赖域算法

3.3算法的收敛性

参考文献

致谢