Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations |
| |
Authors: | X J Zheng X L Sun D Li |
| |
Institution: | 1.Department of Management Science, School of Management,Fudan University,Shanghai,People’s Republic of China;2.Department of Systems Engineering and Engineering Management,The Chinese University of Hong Kong,Shatin, N.T.,Hong Kong |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|