An Optimal D.C. Decomposition Algorithm for Quadratic Program with a Single Quadratic Constraint
F Mathematics · Or Transactions · 2009
We present in this paper an exact method for singly quadratically constrained nonconvex quadratic program(QCQP).This method is based on an optimal D.C. decomposition where the objective function is decomposed into the difference of two convex quadratic functions.Underestimating the concave term of the D.C.decomposition, we obtain a convex QCQP relaxation.We prove that the optimal D.C.decomposition can be found by solving an SDP problem.The exact solution of the orginal problem is then obtained by finding the optimal solution of the corresoonding convex QCQP that satisfies certain complementarity condition.Finally,we report some preliminary numerical results.