非线性互补问题的光滑化牛顿型方法研究

论文摘要

互补问题自1963年首次提出以后便得到了广大研究者的重视,一直是数学规划研究中较为活跃的分支,无论是理论研究还是数值算法,近年来都取得了丰硕的成果。本文主要基于各种光滑牛顿法的思想和光滑理论,针对F为P0函数的情况,介绍一种新的光滑互补函数,将互补问题转化为求解一系列光滑的非线性方程组,然后用牛顿法的思想进行求解,从而得到了求解互补问题的一类光滑牛顿算法;为了确保Φ′（x）的非奇异性,结合Broyden族校正方法,提出了求解非线性互补问题的Broyden族光滑化方法。在较弱的条件下,此算法具有全局收敛性和局部超线性收敛性。对于奇异的非线性互补问题,即F有可能是病态的情形,结合正则化的思想,把原互补问题转化为一个良态的非线性互补问题NCP（Fμ）,并以扰动参数μ作为光滑参数,从而得到一个新的求解非线性互补问题的正则化光滑牛顿算法,此算法要求在F为P0函数的假设下,才能可行且具有较好的收敛性。而对于一股的非线性互补问题,为了去掉这个假设,当牛顿步不可解时,本文将结合梯度步对上述正则化光滑牛顿算法进行改进,从而得到求解一般非线性互补问题的修正Jacobian光滑化方法,此算法具有全局收敛性。在解点R正则的条件下,该算法还具有超线性和局部二次收敛性。数值结果表明,上述的算法具有全局收敛性,并在一定的条件下,均能达到超线性/二次收敛性。全文共分七章,各部分内容安排如下:第一章是绪论部分,介绍互补问题的应用背景和近年来有关互补问题求解的方法;第二、三、四、五章为本文的重点,着重介绍了求解非线性互补问题的四种相关的算法及其收敛性,这四种算法分别为一步光滑牛顿法、Broyden族光滑化方法、正则光滑牛顿法和修正Jacobian光滑化方法;第六章是数值实验,通过互补问题典型的数值算例,进一步说明了本文算法具有良好的收敛性和有效性;最后是对本文的总结和对将来研究工作的展望。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 互补问题概述
• 1.2 算法的研究背景
• 1.3 本文主要工作及内容安排
• 1.4 符号介绍
• 0函数非线性互补问题的一步光滑牛顿法'>第二章 P₀函数非线性互补问题的一步光滑牛顿法
• 2.1 引言
• 2.2 一个新的光滑函数及其性质
• 2.3 算法和预备知识
• 2.4 全局收敛性
• 2.5 超线性/二次收敛性
• 2.6 结论
• 0非线性互补问题的光滑Broyden方法'>第三章 P₀非线性互补问题的光滑Broyden方法
• 3.1 引言
• 3.2 算法和预备知识
• 3.3 收敛性分析
• 3.4 结论
• 0非线性互补问题的正则光滑牛顿法'>第四章 P₀非线性互补问题的正则光滑牛顿法
• 4.1 引言
• 4.2 预备知识
• 4.3 正则光滑牛顿法
• 4.4 收敛性分析
• 4.4.1 全局收敛性
• 4.4.2 收敛性分析
• 4.5 结论
• 第五章 非线性互补问题的修正Jacobian光滑化方法
• 5.1 预备知识及算法
• 5.2 收敛性分析
• 5.3 结论
• 第六章 数值实验
• 6.1 关于一步光滑牛顿法的数值结果
• 6.2 关于光滑Broyden方法的数值结果
• 6.3 关于正则光滑牛顿法的数值结果
• 第七章 结论与展望
• 参考文献
• 致谢
• 作者在攻读硕士期间的主要研究成果