【作者】 陈小红；

【导师】 马昌凤；

【作者基本信息】 桂林电子科技大学 ， 应用数学， 2008， 硕士

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

【Abstract】 Complementarity problem was first proposed in 1963. Since then it has been the hotspot in the research of mathematical programming. Also many algorithms have been proposed. With the idea of smoothing Newton method, we proposed a class of new smoothing Newton methods for solving nonlinear complementarity problem based on a class of smoothing NCP functions.In this paper, NCP is converted into a series of smoothing nonlinear equations and Newton method is used to solve the equations. Under the assumption that F is a P₀ function, we propose a new smoothing Newton method based on a new smoothing NCP function. On the other hand, also we introduce a new Broyden-like method in this paper. The algorithm considered here is based on the smooth approximation Fischer-Burmeister function function and make use of the line search rule of Donghui Li in.In this paper, also we proposed a regularization smoothing Newton method for singular nonlinear complementarity problems by introducing a perturbed positive parameterμ, which is also smoothing parameter. Without the assumption that F is P₀ function, we propose a new smoothing Newton method underlying the Newton equation is unsolvable by modifying the regularization smoothing Newton method. The introduction of Kanzow and Pieper’s gradient step makes our algorithm to be globally convergent. Under R-regularity, the method has a quadratic/superlinearly convergence rate. Under suitable conditions, all our methods achieve fast local convergence rate globally and superlinearly.The paper contain seven parts. In the fist chapter, the application background and the main algorithms of the complementarity problems is introduced. The second, third, forth and fifth sections are the most important parts of this paper, in which four algorithms are detailed for solving nonlinear complementarity problem, also the global and local convergence is established for method. In the sixth chapter, we propose some numerical experiment, and the results show the effectiveness of the proposed algorithms. In the last chapter, we conclude the paper.更多还原