Conic Programming Over Cones Of Nonnegative Quadratic Functions

Cone of nonnegative quadratic functions is the cone of all quadratic functionsbeing nonnegative over a given feasible set. It is an extension of the well-known posi-tive semidefinite cone and copositive cone. Any quadratic programming problem canbe transformed to a conic programming problem over cones of nonnegative quadraticfunctions. Hence, it can further improves the development in quadratic programmingby study the conic programming over cones of nonnegative quadratic functions.In the literature, Lagrangian dual method and semidefinite relaxation method aretwo of the most important tools for studying quadratic programming. However, thesetwo methods have some limitations, especially for non-convex cases, they usually in-troduce a nonzero duality gap or slack gap. In order to overcome the limitations oftraditional methods, this thesis will use the theory of cones of nonnegative quadraticfunctions to study quadratic programming. In this thesis, we establish the theoreti-cal connections between programming problems over cones of nonnegative quadraticfunctions and quadratic programming problems, and then study the global optimal-ity conditions, solvable subclasses and relaxation methods of quadratic programmingfrom the view point of linear conic programming. Based on this research direction,we propose new global optimality conditions for quadratically constrained quadraticprogramming and0-1quadratic programming. These new conditions are more generalthan the positive semidefiniteness condition in the literature. We also propose a newpolynomial time solvable subclass of quadratic programming problems, which expandspreviously known solvable cases. To solve conic programming problems over cones ofnonnegative quadratic functions, we design an adaptive approximation scheme, whichcan automatically improve the approximation efectiveness based on the properties ofgiven problem instances. The convergence property of this scheme is proved. Somenumerical examples are shown to demonstrate the efectiveness of this scheme.The main contributions of the thesis are: By constructing the theoretical connections between conic programming prob-lems over cones of nonnegative quadratic functions and the Lagrangian multi-plier of quadratic programming problems, we propose a new global optimalitycondition, which is more general than the positive semidefiniteness condition inthe literature, for quadratic programming.Based on the algorithms for conic programming, we propose a new algorithm tosolve a subclass of quadratic programming problems. This result extends previ-ously known solvable class to more general cases.To solve the conic programming problems over cones of nonnegative quadraticfunctions, we design an adaptive approximation scheme, which can automati-cally improve the approximation efectiveness for given instances.