求解非线性互补问题的ODE型滤子方法

发布时间：2018-03-21 12:18

本文选题：非线性互补问题　切入点：ODE　出处：《河北大学》2017年硕士论文　论文类型：学位论文

【摘要】：非线性互补问题是指这样的问题:被其包含的两组决策变量之间满足一种互补关系,根据问题中变量所满足的条件的不同,以及互补关系的不同形式,互补问题存在很多种类型,本文主要讨论一般的非线性互补问题.这类问题有着广泛的应用背景,诸如纯交换的竞争经济的均衡问题、具有生产和投资的经济均衡问题、工程中的电路联结问题、流体力学问题、最优控制问题等.因此对非线性互补问题求解具有重要意义.本文将非线性互补问题转化为约束优化问题,而对于约束优化问题的求解,Fletcher和Leyffer曾提出了一类仿照多目标优化的滤子方法,在这类传统的方法中搜索方向都是通过求解序列二次规划子问题得到的,这使得算法运算量比较大.另一方面,传统滤子方法中的点对只包含了目标函数的信息,并没有充分利用其他信息.考虑到上述二次子问题运算量大以及滤子点列信息利用不充分的问题,借助于常微分方程(ODE)方法,利用求解一个非线性方程来计算搜索方向,在改造的滤子集合基础上,提出了求解非线性互补问题的两种算法,一种是将NCP函数信息引入到滤子集合中,提出带有一般NCP函数的ODE型滤子方法.另一种是将NCP函数光滑化,给出光滑化算子的更新公式,从而得到光滑化的ODE型滤子方法.本文中所提出的方法,与传统的滤子方法相比,更为灵活且便于实现,同时算法的计算量相对减少.在合理的假设前提下,我们证明了算法的全局收敛性.
[Abstract]:A nonlinear complementarity problem is a problem in which the two sets of decision variables contained therein satisfy a complementary relationship, depending on the conditions of the variables in the problem, as well as the different forms of the complementary relationship. There are many types of complementarity problems. This paper mainly discusses general nonlinear complementarity problems, which have a wide application background, such as the equilibrium problem of pure exchange competitive economy, the economic equilibrium problem with production and investment. The problems of circuit connection, hydrodynamics, optimal control and so on in engineering are very important for solving nonlinear complementarity problems. In this paper, nonlinear complementarity problems are transformed into constrained optimization problems. For constrained optimization problems, Fletcher and Leyffer have proposed a kind of filter method that mimics multi-objective optimization. In this kind of traditional method, the search direction is obtained by solving the sequential quadratic programming subproblem. On the other hand, the point pairs in the traditional filter method only contain the information of the objective function. Considering the problem that the quadratic subproblem has a large amount of computation and the information of filter points is not sufficiently utilized, the search direction is calculated by solving a nonlinear equation with the aid of ordinary differential equation (ODE) method. On the basis of the modified filter set, two algorithms for solving nonlinear complementarity problems are proposed. One is to introduce the information of NCP function into the filter set, and the other is to smooth the NCP function by introducing the information of ODE filter with general NCP function. The updating formula of smoothing operator is given, and the smoothing ODE filter method is obtained. Compared with the traditional filter method, the method presented in this paper is more flexible and convenient to realize. At the same time, the computational complexity of the algorithm is relatively reduced. On the premise of reasonable assumption, we prove the global convergence of the algorithm.
【学位授予单位】：河北大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221.2

【参考文献】