Optimization Online


A Novel Approach for Solving Convex Problems with Cardinality Constraints

Goran Banjac(goran.banjac***at***eng.ox.ac.uk)
Paul Goulart(paul.goulart***at***eng.ox.ac.uk)

Abstract: In this paper we consider the problem of minimizing a convex differentiable function subject to sparsity constraints. Such constraints are non-convex and the resulting optimization problem is known to be hard to solve. We propose a novel generalization of this problem and demonstrate that it is equivalent to the original sparsity-constrained problem if a certain weighting term is sufficiently large. We use the proximal gradient method to solve our generalized problem, and show that under certain regularity assumptions on the objective function the algorithm converges to a local minimum. We further propose an updating heuristic for the weighting parameter, ensuring that the solution produced is locally optimal for the original sparsity constrained problem. Numerical results show that our algorithm outperforms other algorithms proposed in the literature.

Keywords: non-convex optimization, sparse solution, cardinality constraints, proximal gradient method, convergence

Category 1: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 03/30/2017
Entry Accepted: 03/30/2017
Entry Last Modified: 03/30/2017

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