Optimization Online


Convex optimization under combinatorial sparsity constraints

Christoph Buchheim (christoph.buchheim***at***tu-dortmund.de)
Emiliano Traversi (emiliano.traversi***at***lipn.univ-paris13.fr)

Abstract: We present a heuristic approach for convex optimization problems containing sparsity constraints. The latter can be cardinality constraints, but our approach also covers more complex constraints on the support of the solution. For the special case that the support is required to belong to a matroid, we propose an exchange heuristic adapting the support in every iteration. The entering non-zero is determined by considering the dual of the given convex problem where the variables not belonging to the current support are fixed to zero. While this algorithm is purely heuristic, we show experimentally that it often finds solutions very close to the optimal ones in the case of the cardinality-constrained knapsack problem and for the sparse regression problem.

Keywords: Sparse Optimization, Cardinality Constrained Knapsack, Sparse Regression, Matroids

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Combinatorial Optimization (Graphs and Matroids )


Download: [PDF]

Entry Submitted: 04/01/2018
Entry Accepted: 04/01/2018
Entry Last Modified: 07/18/2019

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