Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations

Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations

0.00 Avg rating0 Votes
Article ID: iaor20117996
Volume: 50
Issue: 4
Start Page Number: 695
End Page Number: 712
Publication Date: Aug 2011
Journal: Journal of Global Optimization
Authors: , ,
Keywords: optimization, matrices, heuristics
Abstract:

We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we use rank‐one matrices and constraint matrices to decompose the indefinite quadratic objective into a D.C. form and underestimate the concave terms in the D.C. decomposition formulation in order to get a convex relaxation of the original problem. We show that the best D.C. decomposition can be identified by solving an SDP problem. By suitably choosing the rank‐one matrices and the linear underestimation, we are able to construct convex relaxations that dominate Shor’s SDP relaxation and the strengthened SDP relaxation. We then propose an extension of the D.C. decomposition to generate an SDP bound that is tighter than the SDP+RLT bound when additional box constraints are present. We demonstrate via computational results that the optimal D.C. decomposition schemes can generate both tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically constrained quadratic problems.

Reviews

Required fields are marked *. Your email address will not be published.