Optimization Online


Successive Convex Approximations to Cardinality-Constrained Quadratic Programs: A DC Approach

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

Abstract: In this paper we consider a cardinality-constrained quadratic program that minimizes a convex quadratic function subject to a cardinality constraint and linear constraints. This class of problems has found many applications, including portfolio selection, subset selection and compressed sensing. We propose a successive convex approximation method for this class of problems in which the cardinality function is first approximated by a piecewise linear DC function (difference of two convex functions) and a sequence of convex subproblems are then constructed by successively linearizing the concave terms of the DC function. Under some mild assumptions, we establish that any accumulation point of the sequence generated by the method is a KKT point of the DC approximation problem. We show that the basic algorithm can be refined by adding valid inequalities in the subproblems. We report some preliminary computational results which show that our method is promising for finding good suboptimal solutions and is competitive with some other local solution methods for cardinality-constrained quadratic programs.

Keywords: Quadratic program; cardinality constraint; DC approximation; successive convex approximation; valid inequalities

Category 1: Nonlinear Optimization

Category 2: Global Optimization

Category 3: Integer Programming


Download: [PDF]

Entry Submitted: 04/03/2012
Entry Accepted: 04/03/2012
Entry Last Modified: 04/16/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