线性约束优化问题的仿射信赖域子空间算法

摘要

最优化理论与方法是决策科学和系统分析中的一个重要工具，在很多领域都有着非常广泛的应用。本文主要研究线性等式和不等式约束的非线性优化问题，提出了结合内点回代线搜索技术的仿射信赖域子空间算法。 信赖域策略是求解非线性规划问题的两种基本逼近方法之一，它能保证算法的整体收敛性。对于无约束优化问题，信赖域方法的思想非常简单与直观。但是，对于约束优化问题，由于约束的存在，通常很难构造一个类似的信赖域子问题。最近，Coleman和Li针对仅带有线性不等式约束的优化问题，提出了“双信赖域方法”(TRAM)，通过仿射变换，成功地构建了一个近似二次模型函数和信赖域子问题，同时证明了算法的整体收敛性，然而文中并未具体给出求解信赖域子问题的方法，且在每次迭代过程中，往往要重复多次求解该子问题，才能获得可接受的严格内点可行步，因此，每得到一新的迭代步，必带来较大的计算量。为克服在求解信赖域子问题时所面临的一系列困难，本文将借助于子空间技术，信赖域算法及内点回代线搜索技术来搜索得到一个严格内点可行步。信赖域子空间技术的应用使得本算法适用于求解大型的约束优化问题。 本文先对一些相关概念、理论及方法进行简单的回顾，作为进一步研究的基础。接着引进一个仿射变换矩阵，同时构建一个近似二次模型函数和信赖域子问题。受到子空间技术的启发，我们给出二维子空间的具体形式，并结合子空间求解信赖域子问题，从而获得模型的一个候选的迭代方向，然后沿此方向通过线搜索获得步长因子，既能保证迭代点严格可行，又能使目标函数在迭代点处单调下降。最后基于信赖域子空间算法的良好性质，在合理的假设条件下，证明了该算法不仅具有整体收敛性，而且保持局部超线性收敛速率。数值计算结果表明了算法的有效性。

目录

文摘

英文文摘

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

声明

第一章最优化问题基本概念

1.1最优化问题简介

1.2最优化方法的结构

1.3两类常用的最优化的整体收敛性方法简介

1.3.1线搜索方法

1.3.2信赖域方法

1.4信赖域子空间算法简介

第二章线性约束问题的仿射内点信赖域子空间算法

2.1引言

2.2信赖域子空间问题的近似最优解

2.2.1负曲率方向的构造

2.2.2子空间的构造

2.2.3子问题的近似最优解的确定

第三章算法

第四章整体收敛性

第五章局部收敛速率

第六章数值结果

第七章小结

参考文献

致谢

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