Linear Conic Reformulation Of Quadratic Programming: Theory And Algorithms

Quadratic programming problem is a kind of classical nonlinear programmingproblems. It is of great importance because of its theoretical interest and wide applica-bility. It includes the binary constrained quadratic integer programming problem, lin-early or quadratically constrained quadratic programming problem, first-order cone orsecond-order cone constrained quadratic programming problem and some other prob-lems from economic management or communication. Linear conic programming prob-lem is a linear programming problem defined over a cone structure. It can equivalentlyrepresent any quadratic programming problem in term of the same optimal objectivevalue. Since linear conic programming belongs to the field of convex programmingand its difculty primarily lies in the cone structure, the study of linear conic program-ming can provide a new perspective on studying quadratic programming. Therefore,recently it has been studied comprehensively and intensively.In the literatures, semidefinite programming and duality theory are two of themost important tools to study quadratic programming. However, they both have somelimitations. Linear conic programming is an extension of traditional semidefinite pro-gramming. Based on the definition of the cone of nonnegative quadratic functions, weestablish the linear conic reformulation for general quadratically constrained quadraticprogramming problems. As the general cone of nonnegative quadratic functions is in-tractable, it can be approximated by tractable cones. During the approximation process,linear matrix inequalities can accelerate the convergence quickly. Therefore, the valid-ness of linear matrix inequalities over diferent approximation cones is studied in thethesis. Extended sufcient global optimality conditions are also presented. Accordingto the theoretical results, we design efcient algorithms using an adaptive scheme tosolve first-order cone constrained quadratic programming problems, and second-ordercone and linear equality constrained quadratic programming problems, respectively.Numerical results indicate the efectiveness of our theory and algorithms. Finally, the contributions and novelties of the dissertation are summarized as fol-lows.(1) Based on the linear conic reformulation of general quadratic programming prob-lems, we study systematically the sufcient and necessary conditions of the valid-ness of linear matrix inequalities over diferent approximation cones. Extendedsufcient global optimality conditions are further proposed based on linear ma-trix inequalities;(2) We deeply study the properties, complexity and algorithms of first-order coneconstrained quadratic programming problems;(3) For second-order cone and linear equality constrained quadratic programmingproblems, we design a polynomial-time algorithm when the feasible region isbounded. When the feasible region is unbounded, two sufcient conditions arepresented to assure that the optimal solution of the original problem can be ob-tained in polynomial time.