
arXiv: 1608.02096
In this paper, we present new convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. While recent research has focused on strengthening convex relaxations using reformulation-linearization technique (RLT), the state-of-the-art methods lose their effectiveness when dealing with (multiple) nonconvex quadratic constraints in QCQP. In this research, we decompose and relax each nonconvex constraint to two second order cone (SOC) constraints and then linearize the products of the SOC constraints and linear constraints to construct some effective new valid constraints. Moreover, we extend the reach of the RLT-like techniques for almost all different types of constraint-pairs (including valid inequalities by linearizing the product of a pair of SOC constraints, and the the Hadamard product or the Kronecker product of two respective valid linear matrix inequalities), examine dominance relationships among different valid inequalities, and explore almost all possibilities of gaining benefits from generating valid constraints. Especially, we successfully demonstrate that applying RLT-like techniques to additional redundant linear constraints could reduce the relaxation gap. We demonstrate the efficiency of our results with numerical experiments.
Convex programming, nonconvex quadratically constrained quadratic programming, reformulation-linearization technique, Nonlinear programming, Optimization and Control (math.OC), SOC-RLT, FOS: Mathematics, 90C20, 90C22, 90C25, 90C26, 90C30, Quadratic programming, convex relaxations, Mathematics - Optimization and Control
Convex programming, nonconvex quadratically constrained quadratic programming, reformulation-linearization technique, Nonlinear programming, Optimization and Control (math.OC), SOC-RLT, FOS: Mathematics, 90C20, 90C22, 90C25, 90C26, 90C30, Quadratic programming, convex relaxations, Mathematics - Optimization and Control
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
