关于非线性互补问题的filter算法研究

论文摘要

以往在处理带约束优化问题时,都要用到Lagrangian函数或罚函数.但是,有时候会产生一些新问题.如乘子的处理,罚参数过大引起的Hessiar阵病态.为了避免这些困难,提出了filter方法.它是一种无乘子和罚参数的方法.非线性规划的filter方法,首先由R. Fletcher和S. Leyfer于1997年提出.由于数值结果很好而受到重视.Filter方法的基本思想是:为得到下一试探步,我们降低目标函数值或约束违反度.若目标函数值和约束条件都变坏(即目标函数值和约束违反度都比以前任何一点大),则该点被当做不成功迭代点.否则,该点被当做成功迭代点.Filter方法的最大优点是:第一、能有效地平衡目标函数与约束条件的关系;第二、Filter方法是一种无乘子方法.第三、Filter方法是一种非单调方法,这有利于得到全局最优点.本文从多目标的角度将filter方法应用于求解非线性互补问题(NCP),并提出了三种算法.对每一种算法,都给出了算例.我们的数值结果表明,我们的算法是成功的.在第二章中,我们提出了一种带双参数(εk和βk)的新filter算法,其中序列{εk}是单调下降的,并且当k充分大时,εk→0.并且证明了,在适当条件下,算法具有超线性收敛性和二阶收敛性.在第三章中,我们提出了一个求解NCP问题的filter内点算法,在主算法中使用Armijio型线搜索求取步长,在修复算法中使用信赖域方法进行适当控制以保证算法的收敛.最后证明了算法的全局收敛性.在第四章里,我们提出了一种基于无导数线搜索的求解NCP问题的filter方法.当一个新点不被filter接受时,我们使用修复算法得到一个新点.在算法的收敛性分析中,我们证明了在较弱假设条件下,算法具有全局收敛性.并且在适当条件下,得到了算法的超线性收敛性.

论文目录

• 摘要
• Abstract
• 第一章 Filter方法与非线性互补问题概述
• 1.1 互补问题数值方法简述
• 1.1.1 内点法和减势法
• 1.1.2 非光滑方程组法
• 1.1.3 光滑方程组法
• 1.1.4 投影类方法
• 1.2 Filter技术
• 1.2.1 非线性优化filter方法的起源，思想和SQP-filter方法
• 1.2.2 模式搜索filter方法
• 1.2.3 内点filter方法
• 1.2.4 其它filter方法
• 1.3 本文主要工作
• 第二章 基于双参数求解NCP问题的filter方法
• 2.1 引言
• 2.2 预备知识
• 2.2.1 NCP函数的特性
• 2.2.2 Filter技术
• 2.3 NCP-filter算法
• 2.4 收敛性分析
• 2.5 数值实验与结论
• 第三章 求解NCP问题的filter内点算法
• 3.1 引言
• 3.2 预备知识
• 3.2.1 基本性质
• 3.2.2 Filter技术
• 3.3 Filter内点算法
• 3.4 收敛性分析
• 3.5 数值实验与结论
• 第四章 基于无导数线搜索求取步长的filter方法
• 4.1 引言
• 4.2 预备知识
• 4.2.1 NCP-函数的一些基本性质
• 4.2.2 无导数线搜索
• 4.2.3 Filter技术
• 4.3 基于无导数线搜索求取步长的filter算法
• 4.4 收敛性分析
• 4.5 数值实验和结论
• 第五章 结论与展望
• 参考文献
• 致谢
• 作者在攻读硕士期间的主要研究成果