A Differential Equation Approach Based On The Space Transformation Of Square Function To Convex Quadratic Programming

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.