非线性互补及推广问题的理论与算法.pdfVIP

摘 要 摘 要 互补问题是在一定空间内寻找满足非负关系和互补关系的函数或变量，这种关系是 一种广泛存在的关系。互补问题从 1963 年被首次提出以来，其理论成果不断丰富发展， 继而成为数学规划中的重要分支和组成部分，同时对其算法的研究也不断改进和完善。 本文主要探讨了非线性互补问题和广义非线性互补问题两类修正的算法。 事实上，解决非线性互补问题的方法有很多，现有文献中给出的绝大部分方法是利 用价值函数将非线性互补问题转化为等价的无约束优化问题或转化为等价的非线性方 程组，不同的价值函数将转化为不同的光滑或者非光滑的方程组，这类方法在实际应用 上不太容易控制，基于这些缺点，本文将现有的非线性互补问题的解法做进一步的改造， 即结合 SPN 分解方法，提出改进滤子算法，以达到减少运算量，并且与无滤子算法比 较，具有更好的实验结果。 非线性互补问题的直接推广即广义非线性互补问题 (generalized nonlinear complementarity problem，)简记为 GNCP，对于 GNCP 的解法，人们经常把它转化为等 价的约束优化问题，但基于目标函数结构复杂，使它的 hessian 矩阵计算比较困难，于 是本文利用互补问题和方程组的等价性，提出了一类修正牛顿型方法，并在较弱的条件 下得到新算法的全局收敛性和局部收敛性。 关键词 非线性互补 广义非线性互补 NCP 函数 牛顿方法 滤子方法 I Abstract Abstract Complementarity problem is to find a variable or a function that satisfies a certain nonnegative property and complementary relationship which are common exists in our daily life. The related theories about the NCPs have developed and been the most important part of Mathematical Programming since it was proposed first in 1963. In this paper, we focus on the modified and improvement approaches of the nonlinear complementarity problem and generalized problem Many algorithms have been proposed for solving nonlinear complementarity problem. One of the powerful approaches is using merit function to reformulate the nonlinear complementarity problem as an equivalent unconstrained optimization problem or as an equivalent system of nonlinear equations. Many kinds of merit functions appear to lead to a system of smoothing equations and no smoothing equations. Actually, the pra