Convex Relaxations and Reformulations for Cardinality Constrained Quadratic Programs

摘要

We present convex relaxations and reformulations for cardinality constrained quadratic programs (CCQP). We first propose a Lagrangian relaxation for (CCQP) via copying constraints. We then show that the Lagrangian relaxation can be reduced to a semidefinte positive (SDP) problem. In particular, for a given parameter, the Lagrangian relaxation can be reduced to to second-order cone (SOCP) problem, which can be viewed as a continuous relaxation of a reformulation of problem (CCQP). Comparison results of different relaxations for (CCQP) are reported in our numerical tests.