凸约束的非线性方程系统的仿射内点信赖域法

摘要

最优化问题是在有限种或无限种可行方案中挑选出最优的方案。它在工农业、国防、交通、金融、通信等领域都有着广泛的应用。伴随着计算机的高度发展和软件的完善，解决最优化问题在生产和生活的各个方面变得越来越重要，也成为现实。 求解最优化问题的方法有很多种，其中线搜索技术与信赖域策略是保证算法的全局收敛性的两个重要手段。本文主要针对凸约束，尤其是有界变量约束的非线性方程系统，将其转换成最优化问题，提出了各类结合非单调线搜索技术的内点信赖域法。 现代信赖域方法的基本思想是在当前迭代点的某个邻域(称为信赖域)内极小化目标函数的一个合适的二次模型，并反复校正信赖域半径，得到可接受方向步。对于仅带有线性不等式的约束优化问题，Coleman和Li在[6]提出了“双信赖域方法”，巧妙地构造了一个仿射变换矩阵，以及合理的近似二次函数和信赖域子问题，克服了不等式约束带来的困难。Heinkenschloss et al.在文献[20]中提出了一类仿射矩阵，得到了与此有关的一阶必要条件。而文献[13]中给出的仿射矩阵则帮助我们在求解信赖域子问题时不涉及有界约束。 本文给出了求解有界约束的非线性方程组的非单调信赖域内点算法。在求解子问题的过程中，通过引入一个仿射矩阵巧妙的去掉了有界约束，从而将原子问题转换成一个只具有椭球约束的信赖域子问题。解此子问题即得严格位于可行域内部的点，通过非单调线搜索获得下一迭代点并保证其有足够下降量。在合理的假设条件下，所给出的这类算法具有全局收敛性和超线性收敛速率。数值结果表明了算法的有效性。 共轭梯度法是解优化问题时的一类常用方法，由于具有算法简便，只需一阶信息，易于编程以及存储空间小等优点，共轭梯度法已经成为求解大规模问题的一种主要方法。Bulteau与Vial在[3]中构造了无约束最优化问题的共轭梯度路径，其基本思想是将标准共轭方向法应用于无约束优化目标函数的局部二次近似函数，得到一组共轭方向序列。共轭梯度路径即为该共轭方向序列的线性组合。在本文中，我们引入另一类仿射变化矩阵，构造了共轭梯度路径。考虑将信赖域子问题中的信赖域约束去掉，沿着这条路径搜索得到迭代方向。当该迭代方向步不严格可行时。利用非单调回代线搜索技术得到可接受的步长因子，并且此步长因子保证了新的迭代点有足够的下降量并且位于可行域的内部。证明了当共轭梯度路径中的参数趋于无穷时，产生的搜索方向即为牛顿步或拟牛顿步从而具有超线性收敛速率。数值测试表明算法的可行性与有效性。 Lanczos方法和共轭梯度路径法的思想启迪我们，对优化问题的近似二次模型应用Lanczos方法过程中同时应用共轭梯度法，即对问题三对角化的同时也计算出了共轭方向序列，这样我们可以得到Lanczos方向序列和共轭方向序列，由此生成一条新的路径，这里命名为Lanczos路径。这条路径有类似于共轭梯度路径的一些重要性质，这对于算法的整体收敛性和超线性收敛性的分析很重要。利用仿射Lanczos路径法求解有界变量约束非线性方程组能大大的减少计算量，在合理的假设下，本文也证明了这类算法具有整体收敛性和局部超线性收敛速率。数值测试结果表明了算法的有效性和稳定性。投影梯度法是解决最优化问题的又一类方法[4，5]，算法虽然具有较快的收敛速度，但每次迭代可能要计算几次投影，这样大大增加了工作量。文献[9]与[36]给出了每次只需计算一次投影的算法。在求解问题的最优化方法中，在最优点x*处的非奇异假设是一个常用的条件([36])，文献[24，40]中，用Levenberg-Marquardt法求解凸约束非线性方程组时把非奇异假设用一个较弱的条件——局部误差界条件来代替。受此启发，改变[36]中所提供的投影牛顿法中的投影区域类似的得到投影牛顿步并结合局部误差界这一条件，本文给出了局部误差界的有界约束非线性方程组的非单调信赖域算法。证明了算法全局收敛性并且证明了在局部误差界这一较弱条件下算法具有超线性收敛速率。数值实验表明了以上所给算法的可行性和有效性。 对于具有一般凸约束的非线性方程组。[9]给出了求一般凸约束的投影梯度算法，参考此文得到搜索方向，并通过求解一个简单的信赖域子问题得到搜索步长，得到求解凸约束非线性方程组的非单调信赖域算法，证明了算法在合理假设下全局收敛且在满足增长条件(局部误差界的特殊形式)下算法超线性收敛。本文给出的凸约束非线性方程组的投影信赖域算法主要参考了文献[4]与[42]中的算法，避免直接求解信赖域子问题，通过近似求解满足两个与信赖域相关条件的步进而得到搜索方向，再通过一维搜索得到下一迭代点。所提供的投影信赖域算法全局收敛且在局部误差界条件下算法具有1.5阶的收敛速率。算法的数值测试将作为进一步研究工作。 本文最后对所做工作进行总结并提出了进一步研究方向。

目录

文摘

英文文摘

论文说明：主要符号对照表

声明

第一章最优化理论与方法的基础

1.1最优化问题简介

1.2最优化条件

1.3最优化问题的算法迭代格式

1.4线搜索与信赖域

1.5非线性方程系统

第二章有界变量约束非线性方程组的信赖域内点算法

2.1引言

2.2算法

2.3收敛性分析

2.4局部收敛性质

2.5数值结果与本章小结

第三章仿射内点共轭梯度路径法

3.1变量有界约束问题的一阶必要条件

3.2仿射内点共轭梯度路径算法

3.3算法的收敛性

3.4整体强收敛性和局部收敛速率

3.5数值结果与本章小结

第四章仿射内点Lanczos路径法

4.1 Lanczos方法

4.2仿射内点Lanczos路径算法

4.3整体收敛性分析

4.4 局部收敛性

4.5数值结果与本章小结

第五章局部误差的有界约束非线性方程组的非单调信赖域算法

5.1局部误差界

5.2算法

5.3整体收敛性

5.4局部收敛速率

5.5数值结果与本章小结

第六章凸约束非线性方程组的非单调信赖域算法

6.1引言

6.2算法

6.3全局收敛性

6.4局部收敛速率

6.5本章小结

第七章凸约束非线性方程组的投影信赖域算法

7.1投影算子与投影梯度性质的重述与补充

7.2算法

7.3全局收敛性

7.4局部收敛性

7.5本章小结

第八章小结

参考文献

致谢

攻读博士学位期间的研究成果