线性约束优化问题的仿射内点最优路径方法

论文摘要

最优化理论与方法是决策科学和系统分析中的一个重要工具,在很多领域都有着非常广泛的应用。本文主要针对线性的等式和不等式约束的非线性优化问题,提出了结合非单调内点回代线搜索技术的仿射最优路径算法。信赖域策略是解非线性规划问题的基本逼近方法,它能保证算法的整体收敛性。对于无约束优化问题,信赖域方法的思想非常的简单与直观。但是,对于约束优化问题,由于约束的存在,通常很难构造一个类似的信赖域子问题。最近,Coleman 和Li 针对仅具有线性不等式约束的优化问题,提出了”双信赖域方法”(TRAM),通过仿射变换,成功的构建了一个近似二次函数和信赖域子问题,克服了由约束带来的困难,并进一步证明了该方法的收敛性。但是作者并没有给出求解信赖域子问题的具体方法。事实上,对于具有严格可行约束的信赖域子问题,在每一迭代步,往往要重复多次求解该子问题,才能获得可接受的严格内点可行步,因此,每得到一步新的迭代步,总的计算量会很大。为了克服解信赖域子问题时带来的困难,可以借助于曲线路径来搜索,而这些路径可以使用精确或非精确Hesse 矩阵的特征值和特征向量表示出来。本文中,引进仿射变化矩阵,基于一般曲线路径的思想,构造一条特殊的近似于仿射信赖子问题的最优曲线路径。考虑将信赖域子问题中的信赖域约束去掉,沿着这条曲线路径去搜索得到迭代方向。当该迭代方向步不严格可行时,利用非单调回代线搜索技术得到可接受的步长因子,从而获得新的有足够下降量的迭代点。在线搜索求迭代步长的过程中,利用非单调技术得到使目标函数非单调下降的迭代点,因为非单调克服高度非线性化函数的求解问题,从而避免了只使用单调搜索在”峡谷”现象局部最优解被卡的情况。本文先对最优化理论与方法的一些相关概念和理论进行简单的回顾,作为进一步研究的基础,接着给出了仿射最优路径的具体形式。然后,结合最优路径的技巧、内点仿射变换和非单调回代搜索,描述了仿射内点最优路径算法。基于最优路径的良好性质,证明了算法在合理的假设条件下,不仅具有整体收敛性,而且保持局部超线性收敛速率。数值计算结果表明了算法的实际有效性。

论文目录

• 摘要
• ABSTRACT（英文摘要）
• 主要符号对照表
• 第一章 最优化问题基本概念
• 1.1 最优化问题简介
• 1.2 最优性条件
• 1.3 最优化方法的结构
• 1.4 两类常用的最优化的整体收敛性方法简介
• 1.4.1 线搜索方法
• 1.4.2 信赖域方法
• 第二章 线性约束问题的仿射内点最优路径算法
• 2.1 引言
• 2.2 仿射内点最优路径的构造与性质
• 2.2.1 仿射变换最优路径
• 2.2.2 仿射变换最优路径的性质
• 第三章 算法
• 第四章 整体收敛性
• 第五章 局部收敛速率
• 第六章 数值结果
• 第七章 小结
• 致谢及声明
• 攻读硕士学位期间的研究成果
• 论文独创性声明
• 论文使用授权声明