SDP Approximate Algorithm Based On D.C. Decompositions For A Class Of Nonconvex Quadratically Constrained Quadratic Programming Problems

Nonconvex quadratically constrained quadratic programming is an important class of optimization problems with numerous applications in engineering, econ-omy and management, and financial optimization areas, including producing and planning problems, economic scale problem, engineering design and control prob-lems and combined optimization problems. This class of problems include many important and challenging NP-hard optimization problems.In this thesis, we investigate semidefinite programming (SDP) relaxation for nonconvex quadratically constrained quadratic programming. We propose a new SDP method based on D.C. decompositions. The method is based decomposing the objective function into a D.C. function and underestimating the concave terms by linear functions. Two classes of D.C. decomposition schemes are considered: D.C. decomposition based on parametric vectors and D.C. decomposition based on constraint coefficient matrices. We show that finding the best D.C. decompo-sition leads to a SDP relaxation problem to the original problem. We prove that the SDP bound obtained from D.C. decomposition is tighter than the classical Shor's SDP relaxation. We also show that a feasible solution can be obtained by solving a second-order cone problem corresponding to the optimal D.C. de-composition. Computational results show that the SDP relaxation based on the D.C. decomposition schemes generate tighter lower bound and better approxi-mate optimal solutions than the the classical SDP relaxation and randomized method.This thesis is organized as follows. In Chapter 1, we introduce the back-ground of nonconvex quadratic programming and the main research results of the thesis. In Chapter 2, we review the existing algorithms for solving noncon-vex quadratically quadratic programming problems including branch-and-bound algorithm, semidefinite programming relaxation and randomizing approximate algorithm based on SDP relaxation. We present our main results in Chapter 3 in which the SDP relaxation methods based on D.C. decomposition are motivated and derived. In Chapter 4. we present the numerical results of the SDP relaxation based on the D.C. decomposition schemes. Comparison results with the classi-cal SDP relaxation and randomization algorithm are also presented. Finally, we conclude the thesis in Chapter 5 by summarizing the main results of the thesis and discussing some future research topies...