Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach

We consider in this paper quadratic programming problems with cardinality and minimum threshold constraints which arise naturally in various real-world applications such as portfolio selection and subset selection in regression. We propose a new semidefinite program (SDP) approach for computing the ``best'' diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation. We also give an alternative way of deriving the perspective reformulation by applying a special Lagrangian decomposition scheme to the diagonal decomposition of the problem. This derivation can be viewed as a ``dual'' method to the convexification method employing the perspective function on semi-continuous variables. Computational results show that the proposed SDP approach can be advantageous for improving the performance of MIQP solvers when applied to the second-order cone programming reformulation and the perspective cut reformulation of the problem.

Article

Download

View Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach