Research On Algorithms Of Convex Quadratic Programming

Quadratic programming is a kind of very important and active branch in operations research, which has wide applications and is extensively applied in many fields, such as operations research and economical mathematic. Therefore, it is significant to study the algorithms for solving quadratic programming. Researching the algorithms of quadratic programming is not only to solve itself, but also to solve other nonlinear programming, because most optimization algorithms are derived from quadratic function model. This kind of method is often effective in practice problems, mostly because ordinary functions are well closed to quadratic function at the minimum points.The interior point algorithms for convex quadratic programming are dealt with in the thesis mainly, and the convergence of the algorithms is analyzed in detail. The main contributions of the dissertation are as follows:The whole thesis consists of five chapters. Present studying situation of quadratic programming and the research meaning are briefly introduced in chapter one. In order to obtain interior point algorithms for convex quadratic programming, in chapter two, the basic knowledge and theory of quadratic programming are showed, including fundamental concepts, optimization conditions, penalty function and Lagrange function which will be repeatedly applied in the following chapters.In chapter three, quasi-newton methods are introduced, Wolfe-Powell and Armijo linear search are also presented. Based on the theory, a new approach for convex quadratic programming with equality constrains is studied. The new approach improves the step length and the convergence is analyzed. Numerical examples are given to illustrate the effectiveness of the proposed method.In chapter four, the limitation and virtue of penalty function and Lagrange function are analyzed. Based on the primal-dual logarithmic-barrier method, a new algorithm for convex quadratic programming with equality and non-equality constrains is discussed. In this algorithm penalty function and augmented Lagrange function are both used. Meanwhile numerical examples are provided to illustrate the effectiveness of the algorithm.Chapter five concludes the thesis and proposes some problems for further research on the algorithms of the quadratic programming.