滤子方法求解非线性优化问题

论文摘要

非线性（无）约束的最优化理论与方法的研究,由整体收敛性和局部收敛速率两部分构成,其中线搜索技术与信赖域策略是保证算法的整体收敛性的两个重要手段。同时,伴随着计算机的发展和软件的完善,最优化问题的数值求解正变得越来越实际可行。本文主要针对非线性等式约束、非负约束、一般约束优化问题与非线性等式和不等式系统,借助Fletcher和Leyffer提出的滤子思想,将约束优化问题和非线性系统转化为多目标优化问题,提出了各类有效的线搜索滤子方法,求解非线性约束优化问题以及非线性等式和不等式系统。Fletcher和Leyffer针对非线性优化问题提出了滤子方法,从而代替传统的罚函数方法来保证优化算法的整体收敛性。其主要的思想是,当目标函数或约束违反度被改进时,就接受试探点。但是,先前的工作只考虑滤子信赖域方法和算法的整体收敛性。因此,本文将滤子线搜索方法结合两类正割算法求解非线性等式约束优化问题。与一般的滤子方法不同的是,本文用拉格朗日函数代替目标函数作为滤子的组成部分。在保持整体收敛性的情况下,算法具有局部二步Q-超线性收敛速率,而且不需要引入二阶校正步。近期的研究表明,单调的线搜索方法存在一些缺点。尤其是当迭代点到达函数的狭窄谷底时,单调下降的要求可能导致降低收敛速率。Grippo等人推广了Armijo条件,提出了非单调线搜索方法。该方法允许函数值上升,同时保证算法的整体收敛性。数值实验结果证明非单调线搜索方法是有效的、可靠的。本文将滤子正割方法与非单调技术结合求解非线性等式约束优化问题。主要贡献在于将非单调技术应用于滤子和下降条件,使得新方法相对于单调方法更容易接受试探步长,减少了计算量。既约Hessian二次规划算法被证实是求解大规模优化问题的有效方法,尤其是对自由度相对不大的问题。通过空间分解技术,在相对较小的空间里面求解QP子问题,可以大大降低存贮空间和计算量。考虑既约Hessian二次规划算法和由Yu等人提出的非单调技术,本文构造了非单调滤子既约Hessian算法求解非线性等式约束优化问题。在合理假设下,证明了算法具有整体收敛性和二步Q-超线性收敛速率。数值结果表明非单调方法比单调的情形更有效,同时不会受到Maratos效应的影响,即最后几次迭代的步长都是1。内点障碍方法在大规模优化计算当中得到日益重视。与积极集策略不同,这些方法提供了解决不等式约束优化问题的另一种有效手段。本文提出了滤子内点方法求解非线性等式和非负约束优化问题。数值结果表明该算法是可行的。国际上很多学者提出了多维滤子的定义,Gould, Leyffer和Toint用多维滤子的思想求解非线性方程组和非线性最小二乘问题。Gould, Sainvitu和Toint则解决了无约束优化问题的求解。Wachter和Biegler提出了滤子线搜索方法求解等式约束优化问题。由于很多问题同时含有等式和不等式约束,本文基于多维滤子和非单调技术将Wachter-Biegler的方法推广到求解一般约束优化问题。当优化问题只有等式约束和M=1时,该方法就是Wachter-Biegler的方法。数值结果与SNOPT比较,表明新方法是有效的。非线性等式和不等式系统在应用数学领域有大量的应用,在数学建模、优化、互补问题以及变分不等式的数值算法中起着核心地位。作为滤子方法的应用,本文提出了非单调滤子方法求解非线性等式和不等式系统。在合理假设下,该方法具有整体收敛性和局部Q-超线性收敛速率。数值结果与两类信赖域方法比较,表明新方法是有效的,同时,完全步χκ+1=χκ+dκ或χκ+1=χκ+dκc+dκsoc在最后几次迭代中被接受,使得序列{xk}Q-超线性收敛于x*。最后本文对所做的研究工作进行总结,特别是创新点小结,并提出了进一步的研究方向。

论文目录

• 摘要
• ABSTRACT
• 主要符号对照表
• 第一章 最优化理论与方法的基础
• 1.1 最优化问题简介
• 1.2 最优化条件
• 1.3 最优化问题的算法迭代格式
• 1.4 线搜索与信赖域
• 1.5 非线性等式和不等式系统简介
• 第二章 两类滤子正割方法求解非线性等式约束优化问题
• 2.1 引言
• 2.2 算法
• 2.3 整体收敛性
• 2.4 局部收敛性
• 2.5 算法的局部收敛速率
• 2.6 小结
• 第三章 非单调滤子正割方法求解非线性等式约束优化问题
• 3.1 引言
• 3.2 算法
• 3.3 整体收敛性
• 3.4 局部收敛性
• 3.5 数值结果
• 3.6 小结
• 第四章 非单调滤子既约Hessian方法求解非线性等式约束优化问题
• 4.1 引言
• 4.2 算法
• 4.3 整体收敛性
• 4.4 局部收敛性
• 4.5 数值结果
• 4.6 小结
• 第五章 滤子内点方法求解非线性等式和非负约束优化问题
• 5.1 引言
• 5.2 算法
• 5.3 数值结果
• 5.4 小结
• 第六章 非单调多维滤子SQP方法求解一般最优化问题
• 6.1 引言
• 6.2 算法
• 6.3 整体收敛性
• 6.4 局部收敛性
• 6.5 数值结果
• 6.6 小结
• 第七章 非单调滤子方法求解非线性等式和不等式系统
• 7.1 引言
• 7.2 算法
• 7.3 整体收敛性
• 7.4 局部收敛性
• 7.5 数值结果
• 7.6 小结
• 第八章 总结
• 参考文献
• 致谢
• 攻读博士学位期间的研究成果
• 答辩委员会签名