Sparsity Constrained Minimization via Mathematical Programming with Equilibrium Constraints

Abstract

Sparsity constrained minimization captures a wide spectrum of applications in both machine learning and signal processing. This class of problems is difficult to solve since it is NP-hard and existing solutions are primarily based on Iterative Hard Thresholding (IHT). In this paper, we consider a class of continuous optimization techniques based on Mathematical Programs with Equilibrium Constraints (MPECs) to solve general sparsity constrained problems. Specifically, we reformulate the problem as an equivalent biconvex MPEC, which we can solve using an exact penalty method or an alternating direction method. We elaborate on the merits of both proposed methods and analyze their convergence properties. Finally, we demonstrate the effectiveness and versatility of our methods on several important problems, including feature selection, segmented regression, MRF optimization, trend filtering and impulse noise removal. Extensive experiments show that our MPEC-based methods outperform state-of-the-art techniques, especially those based on IHT.

arXiv admin note: text overlap with arXiv:1608.04425

References in corpus (2)

• Binary Optimization via Mathematical Programming with Equilibrium Constraints
• Sparse Prediction with the $k$-Support Norm

Cited by in corpus (9)

• Binary Optimization via Mathematical Programming with Equilibrium Constraints
• A Coordinate-wise Optimization Algorithm for Sparse Inverse Covariance Selection
• Second Order Optimality Conditions and Improved Convergence Results for a Scholtes-type Regularization for a Continuous Reformulation of Cardinality Constrained Optimization Problems
• Fast Large-Scale Discrete Optimization Based on Principal Coordinate Descent
• A Block Decomposition Algorithm for Sparse Optimization
• A Sparsity Algorithm with Applications to Corporate Credit Rating
• Single molecule localization by ${\ell }_2-{\ell }_0$ constrained optimization
• Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence
• Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergence