Optimization Online


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

Xiaojin Zheng (xjzheng***at***tongji.edu.cn)
Xiaoling Sun (xls***at***fudan.edu.cn)
Duan Li (dli***at***se.cuhk.edu.hk)

Abstract: 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.

Keywords: cardinality constrained quadratic programming; perspective reformulation; La- grangian decomposition; semidefinite program relaxation; mixed-integer quadratic program reformulations

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 11/07/2010
Entry Accepted: 11/07/2010
Entry Last Modified: 09/08/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society