Studieso N The Theory And Methods For Continuous And Integer Nonconvex Quadratic Programming Problems

Continuous and integer nonconvex quadratic programming is an important class of optimization problems with numerous applications in engineering, economy and management areas. This class of problems include many important and challeng-ing NP-hard optimization problems such as nonconvex quadratically constrained quadratic problem (QCQP), nonconvex linearly constrained quadratic problem (QP), quadratic integer programming (QIP),0-1 quadratic programming (0-1QP) and quadratic knapsack problem (QKP).This thesis aims to investigate the theory and methods for continuous and in-teger nonconvex quadratic programming. In particular, we study the Lagrangian duality, SDP relaxations and integer diagonalization methods for several impor-tant classes of integer and continuous nonconvex QP. The main contributions of the thesis are as follows:(1) We present new sufficient conditions for verifying zero duality gap in nonconvex quadratically/linearly constrained quadratic programs (QP). We first derive a dual solution based sufficient condition for zero duality gap between a quadratically constrained QP and its Lagrangian dual, while this condition only depends on the information of the optimal dual solution and thus is polynomially checkable. We then use a distance measure to characterize the duality gap for nonconvex QP with linear constraints. We show that this distance can be com-puted via cell enumeration technique in discrete geometry. We also revisit two sufficient optimality conditions in the literature for two classes of nonconvex QPs and show that these conditions actually imply zero duality gap.(2) We investigate the estimates of the duality gap in binary quadratic pro-gramming with linear equality constraints. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP re-laxation, using the distance from{-1,1}n to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyper-plane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the squared norm constraint reformulations are also discussed.(3) We study the semidefinite programming relaxation and Lagrangian re-laxation for quadratic knapsack problems. Optimality conditions for the primal and dual problem are presented. It is shown that the SDP relaxation does not always possess a unique optimal solution. This is in contrast with the uncon- strained 0-1 quadratic problem where the SDP relaxation always has a unique optimal solution. We then derive a necessary and sufficient condition to ensure the uniqueness of the SDP relaxation solution for QKP. The duality gap between QKP and its SDP relaxation is characterized by the distance from set {0,1}n to certain polyhedral set. It is shown that the duality gap can be reduced by an amount proportional to the square of the distance.(4) We propose a new method for checking the feasibility or finding a solution of the linear equations Ax=b over a bounded integer set X via computing the distanceδ, i.e., the distance between set X and set {x∈Rn|Ax=b}. Our method is based on the connection between the computation ofδand the cell enumeration of an arrangement of hyperplanes in discrete geometry. We first show that the linear system Ax=b on binary integer set X={-1,1}n can be solved in O{nn-d) time. Polynomially solvable cases of the linear system on binary integer set are also discussed. We then investigate the general case when X= {-m,...,m}n. We show that finding a solution of Ax=b on X={-m,...,m}n or checking its feasibility can be done in O((2m,n)n-d) time.(5) We present an integer diagonalization approach for deriving new lower bounds for general quadratic integer programming problems. Semi-unimodular transformations are introduced to diagonalize a symmetric matrix and meanwhile preserve integral property of the feasible set. Separable quadratic integer program can then be obtained as a relaxation of the nonseparable quadratic integer pro-gram via semi-unimodular transformation. We introduce the integer diagonaliza-tion dual problem and analyze some basic properties of the set of semi-unimodular transformations for a rational symmetric matrix. A complete characterization of the set of all semi-unimodular transformations for a nonsingular 2×2 symmetric matrix is presented. Lagrangian decomposition and convex relaxation schemes for the relaxed separable quadratic integer programming problem are analyzed and their tightness are compared.(6) We present a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems. Outer approximation and bundle method are used to compute the Lagrangian bound where the Lagrangian relaxation is solved by the maximum flow algorithm. We also present a surrogate constraint heuris-tic for finding feasible solutions. Preliminary computational results for small to medium size test problems are reported.(7) We propose a general convex relaxation scheme via D.C. decomposi- tions for linearly constrained nonconvex quadratic programming problems. We demonstrate an interesting equivalence between the "best" parametric D.C. de-composition, in terms of the tightest convex relaxation via D.C. decomposition, and its corresponding semidefinite relaxation formulation. We gain dual bene-fits from the revealed property between the SDP formulation and the best D.C. decomposition:(ⅰ) Reduction of the iterative dual search process in finding the best D.C. decomposition to a single SDP formulation, and (ⅱ) Identification of a feasible solution of the primal problem by solving the convex relaxation cor-responding to the SDP solution. Three classes of special D.C. decomposition schemes, diagonal perturbation, squared linear constraints, congruence transfor-mation, and their combinations are investigated. Preliminary numerical results are reported to compare the tightness of the lower bounds generated by different D.C. decompositions and other existing lower bounds.(8) We propose several classes of parametric D.C. decompositions for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. For a given class of parametric D.C. decompo-sitions, we identify the best D.C. decomposition in the sense that its associated convex relaxation yields the tightest bound. We show that the best D.C. decom-position can be found by solving a corresponding SDP problem. Especially, we derive an SDP bound, from a D.C. decomposition scheme using the coefficient matrices in the constraints, that dominates Shor's SDP bound. A prominent fea-ture of all these best D.C. decomposition schemes is that a feasible solution can be obtained by solving a convex quadratically constrained quadratic program via second-order cone program. Computational results demonstrate that the optimal D.C. decomposition schemes can generate tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically constrained quadratic problems. Finally, we present an exact algorithm for nonconvex quadratic pro-gram with a single convex quadratic constraint.