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

发布时间：2019-03-31 07:38

【摘要】：互补问题是在一定空间内寻找满足非负关系和互补关系的函数或变量,这种关系是一种广泛存在的关系。互补问题从1963年被首次提出以来,其理论成果不断丰富发展,继而成为数学规划中的重要分支和组成部分,同时对其算法的研究也不断改进和完善。本文主要探讨了非线性互补问题和广义非线性互补问题两类修正的算法。事实上,解决非线性互补问题的方法有很多,现有文献中给出的绝大部分方法是利用价值函数将非线性互补问题转化为等价的无约束优化问题或转化为等价的非线性方程组,不同的价值函数将转化为不同的光滑或者非光滑的方程组,这类方法在实际应用上不太容易控制,基于这些缺点,本文将现有的非线性互补问题的解法做进一步的改造,即结合SPN分解方法,提出改进滤子算法,以达到减少运算量,并且与无滤子算法比较,具有更好的实验结果。非线性互补问题的直接推广即广义非线性互补问题(generalized nonlinear complementarity problem,)简记为GNCP,对于GNCP的解法,人们经常把它转化为等价的约束优化问题,但基于目标函数结构复杂,使它的hessian矩阵计算比较困难,于是本文利用互补问题和方程组的等价性,提出了一类修正牛顿型方法,并在较弱的条件下得到新算法的全局收敛性和局部收敛性。
[Abstract]:Complementarity problem is to find a function or variable that satisfies the non-negative relation and the complementary relation in a certain space. This relation is a kind of widespread relation. Since the complementarity problem was first proposed in 1963, its theoretical achievements have been continuously enriched and developed, and then it has become an important branch and part of mathematical programming. At the same time, the research on its algorithm has also been continuously improved and perfected. In this paper, two kinds of modified algorithms for nonlinear complementarity problem and generalized nonlinear complementarity problem are discussed. In fact, there are many methods to solve the nonlinear complementarity problem. Most of the methods given in the existing literature are to transform the nonlinear complementarity problem into equivalent unconstrained optimization problem or equivalent nonlinear system of equations by using the value function. Different value functions will be converted into different equations of smooth or non-smooth. This kind of method is not easy to control in practical application. Based on these shortcomings, this paper makes a further modification of the solution of the existing nonlinear complementarity problem. Combining the SPN decomposition method, an improved filter algorithm is proposed to reduce the computational complexity. Compared with the non-filter algorithm, the improved filter algorithm has better experimental results. The direct generalization of nonlinear complementarity problem, that is, generalized nonlinear complementarity problem (generalized nonlinear complementarity problem,), is simply written as GNCP, 's solution to GNCP. It is often converted into equivalent constrained optimization problem, but the structure of objective function is complex. It is difficult to calculate its hessian matrix. In this paper, a modified Newton-type method is proposed by using the equivalence of complementary problems and equations, and the global convergence and local convergence of the new algorithm are obtained under weak conditions.
【学位授予单位】：河北大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221.2

【相似文献】