Optimization Online


On two relaxations of quadratically-constrained cardinality minimization

Dennis Wei(dlwei***at***eecs.umich.edu)

Abstract: This paper considers a quadratically-constrained cardinality minimization problem with applications to digital filter design, subset selection for linear regression, and portfolio selection. Two relaxations are investigated: the continuous relaxation of a mixed integer formulation, and an optimized diagonal relaxation that exploits a simple special case of the problem. For the continuous relaxation, an absolute upper bound on the optimal cost is derived, suggesting that the continuous relaxation tends to be a relatively poor approximation. In computational experiments, diagonal relaxations often provide stronger bounds than continuous relaxations and can greatly reduce the complexity of a branch-and-bound solution, even in instances that are not particularly close to diagonal. Similar gains are observed with respect to the mixed integer programming solver CPLEX. Motivated by these results, the approximation properties of the diagonal relaxation are analyzed. In particular, bounds on the approximation ratio are established in terms of the eigenvalues of the matrix defining the quadratic constraint, and also in the diagonally dominant and nearly coordinate-aligned cases.

Keywords: cardinality minimization, mixed integer quadratic programming, relaxation methods, subset selection, portfolio optimization

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

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 10/18/2012
Entry Accepted: 10/18/2012
Entry Last Modified: 10/18/2012

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