Conic Programming Over Cones Of Nonnegative Quadratic Functions: Computability And Application

Quadratically constrained quadratic programming problem and its conic reformu-lation problem have the same optimal value. The conic reformulation problem is aconic programming problem over cones of nonnegative quadratic functions, thus it isworthy of our in-depth research in how to solve such problem. Naturally, we needto study the computability of the cone of nonnegative quadratic functions. This dis-sertation lists that cones of nonnegative quadratic functions over an ellipsoid, over anellipsoid and a linear equality constraint and the cone of nonnegative quadratic formsover a second order cone have linear matrix inequality representations. In what fol-lows, we present the covers for the problems with the feasible region is bounded orunbounded. We give the computable conic relaxation for the primal problem based onthe good properties of cone of nonnegative functions and achieve a lower bound forthe primal problem. In order to achieve a good lower bound, we improve the conicrelaxation problem through improving the covers.This paper solves three types of problems including the quadratic programmingproblem with linear complementarity constraints, detection of a copositive matrix overa p-th order cone and0-1quadratic knapsack problem. The covers are designed accord-ing to the characteristics of diferent problems and corresponding conic approximationalgorithms are provided. All the algorithms are convergent and numerical experimentsshow the efectiveness. It is worth pointing out that we introduce the concept of redun-dant constraints so as to obtain a better lower bound for the primal problem. It showedthat adding redundant constraints can shorten iterations and CPU times through numer-ical experiments.In the following, we will give the main innovations and novelties of this disserta-tion briefly.(1) We prove the cone of nonnegative quadratic functions over an ellipsoid and alinear inequality has linear matrix inequality representations and give a conic approximation method for the0-1quadratic knapsack problem.(2) We prove that detecting the copositivity of a given matrix over a p-th order coneis equivalent to the decision problem of a p-norm constrained quadratic program-ming problem. Then, we identify some polynomial-time solvable subclasses ofthe detection problem.(3) Though the quadratic optimization with linear complementarity constraints is notstrictly feasible, we can find a cover containing an interior point. Furthermore,we can guarantee the new cover can also maintain this nature after the partition,which is a difcult point in designing our conic approximation algorithm. Thisnature means that the conic relaxation problem is strictly feasible which is criticalfor the stability of the interior-point algorithm.