Convex optimization under combinatorial sparsity constraints |
| |
Institution: | 1. Fakultät für Mathematik, TU Dortmund, Vogelpothsweg 87, 44227 Dortmund, Germany;2. LIPN, Université Paris 13, 99 Avenue Jean-Baptiste Clément, 93430 Villetaneuse, France |
| |
Abstract: | We present a heuristic approach for convex optimization problems containing different types of sparsity constraints. Whenever 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 multipliers of the bounds on variables being fixed to zero. While this algorithm is purely heuristic, we show experimentally that it often finds near-optimal solutions for cardinality-constrained knapsack problems and for sparse regression problems. |
| |
Keywords: | Sparse optimization Cardinality constrained knapsack Sparse regression |
本文献已被 ScienceDirect 等数据库收录! |
|