2019/02/13 by Jean‐Philippe Chancelier, Jean-Philippe Chancelier, Michel De Lara +4 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Computer science #Constraint (computer-aided design) #Convex optimization #Convexity #Mathematical optimization #Mathematics #Optimization and Variational Analysis #Optimization problem #Regular polygon #Sparse and Compressive Sensing Techniques #Upper and lower bounds #math.OC
paper · pdf · doi:10.48550/arxiv.1902.04813
published in arXiv (Cornell University) (Cornell University)
arxiv created 2019/02/13 · openalex publication_date 2019/02/13 · arxiv updated 2019/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In exact sparse optimization problems on Rd (also known as sparsity constrained problems), one looks for solution that have few nonzero components. In this paper, we consider problems where sparsity is exactly measured either by the nonconvex l0 pseudonorm (and not by substitute penalty terms) or by the belonging of the solution to a finite union of subsets. Due to the combinatorial nature of the sparsity constraint, such problems do not generally display convexity properties, even if the criterion to minimize is convex. In the most common approach to tackle them, one replaces the sparsity constraint by a convex penalty term, supposed to induce sparsity. Thus doing, one loses the original exact sparse optimization problem, but gains convexity. However, by doing so, it is not clear that one obtains a lower bound of the original exact sparse optimization problem. In this paper, we propose another approach, where we lose convexity but where we gain at keeping the original exact sparse optimization formulation, by displaying lower bound convex minimization programs. For this purpose , we introduce suitable conjugacies, induced by a novel class of one-sided linear couplings. Thus equipped, we present a systematic way to design norms and lower bound convex minimization programs over their unit ball. The family of norms that we display encompasses most of the sparsity inducing norms used in machine learning. Therefore, our approach provides foundation and interpretation for their use.