The Study Of Algorithms For Quadratic Programming

Quadratic programming is an important branch in mathematical programming, which has wide applications in many fields such as operation research, economical mathematics. Therefore, it is significant to study the algorithms for solving quadratic programming problems. The thesis mainly deals with the study of interior point algorithms for convex quadratic programming and analyzes its convergence in detail.The whole thesis consists of five chapters. The formulation and the present studying situation of quadratic programming are briefly introduced in chapter one. In order to obtain interior point algorithms for convex quadratic programming, basic knowledge and theory of quadratic programming are discussed in this chapter, including fundamental concepts, optimization conditions, duality theory and the proof of a series of nonsingular matrixes, which will be repeatedly applied in the following chapters. At last, the author points out that quadratic programming is an NP—hard problem.In chapter two, the strictly feasible interior point algorithm for convex quadratic programming is presented, and its convergence is analyzed.While in chapter three, the infeasible interior point algorithm for convex quadratic programming is presented, and its convergence is analyzed too.In chapter four, the convex quadratic programming is firstly transformed into linear complementarity problem, then the existence conditions of solution to linear complementarity problem are discussed and central path algorithm for linear complementarity problem is given. Meanwhile its convergence is analyzed.In chapter five, the simple method to ball constrained convex quadratic programming is proposed.