【作者】 代小梅；

【导师】 张立卫；

【作者基本信息】 大连理工大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 凸二次规划是数学规划中的一个重要分支,它在经济,市场均衡,管理,军事等各个领域均有重要应用。求解凸二次规划问题有很多有效的算法,如拟牛顿法,内点法,投影法,Langrange方法及Lemke方法等。本文旨在研究求解凸二次规划问题的微分方程方法,包括求解凸二次规划问题的一阶微分方程方法和二阶微分方程方法的理论及相应的数值实现。其原因有三:一是很多优化问题的神经网络方法都由微分方程系统来刻画;二是可以把有效的微分方程数值解法用于求解凸二次规划问题;三是二阶导数的微分方程方法是二次收敛的。本文首先将一般的凸二次规划问题转化为等价的优化问题,然后基于一具体的空间变换利用微分方程进行求解。首先我们对凸二次规划问题建立了一阶微分方程系统,随后我们利用牛顿方法建立了二阶微分方程系统;对于这两个微分方程系统,我们证明了它们具有如下性质:凸二次规划问题的KKT点是它们的渐近稳定平衡点,且当初始点可行时,解轨迹将全部落于可行域中。其次我们还证明了该微分方程系统欧拉离散迭代格式的收敛性。我们还给出了算法,并证明了基于二阶导数的微分方程系统的算法具有二阶收敛速度。最后用两个离散迭代格式计算了几个例子,数值结果验证了微分方程方法的有效性,也表明基于二阶导数的微分方程系统的算法具有较快的收敛速度。更多还原

【Abstract】 The convex quadratic programming is an important branch of mathematical programming. It has important applications in economic, equilibrium market management, military and other fields. There are many effective algorithms to solve quadratic programming problems, including Newton methods, interior point methods, projection methods, Wolfe algorithms, Lagrange methods and Lemke methods.The aim of this dissertation is to study differential equation approaches to convex quadratic programming, including theories and numerical implementations of both first order and second order differential equation approaches. There are three reasons for selecting such a subject: First, this may provide a theoretical support to some neural network methods as there are many neural network for optimization problems characterized by systems of differential equations; Next, effective numerical algorithms for differential equations can be applied to solving convex quadratic programming; At last, the convergence rate of second order derivatives differential equation method is quadratic.For convex quadratic programming, using space transformation, we construct differential equation systems based on first order derivatives and second order derivatives. The two systems are proved to have the properties: the KKT point of a convex quadratic programming is an asymptotically stable equilibrium point of the system and the whole solution trajectory is in the feasible domain of the problem if it starts from a feasible point. Moreover, we demonstrate the convergence theorems for the discrete schemes of the two differential systems, including the locally quadratic convergence rate of the discrete algorithm for second order derivatives based on these two discrete methods and the numerical results show that the differential equation algorithms based on second order derivatives are faster than that on first order derivatives.更多还原