Efficient DC Algorithm for Constrained Sparse Optimization

Abstract

We address the minimization of a smooth objective function under an ${\ell }_0$-constraint and simple convex constraints. When the problem has no constraints except the ${\ell }_0$-constraint, some efficient algorithms are available; for example, Proximal DC (Difference of Convex functions) Algorithm (PDCA) repeatedly evaluates closed-form solutions of convex subproblems, leading to a stationary point of the ${\ell }_0$-constrained problem. However, when the problem has additional convex constraints, they become inefficient because it is difficult to obtain closed-form solutions of the associated subproblems. In this paper, we reformulate the problem by employing a new DC representation of the ${\ell }_0$-constraint, so that PDCA can retain the efficiency by reducing its subproblems to the projection operation onto a convex set. Moreover, inspired by the Nesterov's acceleration technique for proximal methods, we propose the Accelerated PDCA (APDCA), which attains the optimal convergence rate if applied to convex programs, and performs well in numerical experiments.

References in corpus (5)

• Nearly unbiased variable selection under minimax concave penalty
• A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
• Sequential Convex Programming Methods for A Class of Structured Nonlinear Programming
• Further properties of the forward-backward envelope with applications to difference-of-convex programming
• A proximal difference-of-convex algorithm with extrapolation

Cited by in corpus (8)

• The Trimmed Lasso: Sparsity and Robustness
• Hidden Convexity in the l0 Pseudonorm
• A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
• Learning Simple Thresholded Features with Sparse Support Recovery
• Orthant-Strictly Monotonic Norms, Generalized Top-k and k-Support Norms and the L0 Pseudonorm
• L1-Regularized ICA: A Novel Method for Analysis of Task-related fMRI Data
• Optimistic Robust Optimization With Applications To Machine Learning
• Sparse Optimization Problem with s-difference Regularization