Lagrange Dual Method for Sparsity Constrained Optimization

Abstract

In this paper, we investigate the l0 quasi-norm constrained optimization problem in the Lagrange dual framework and show that the strong duality property holds. Motivated by the property, we propose a Lagrange dual method for the sparsity constrained optimization problem. The method adopts the bisection search technique to maximize the Lagrange dual function. For each Lagrange multiplier, we adopt the iterative hard thresholding method to minimize the Lagrange function. We show that the proposed method converges to an L-stationary point of the primal problem. Computational experiments and comparisons on a number of test instances (including random compressed sensing instances and random and real sparse logistic regression instances) demonstrate the effectiveness of the proposed method in generating sparse solution accurately.

Keywords

• Sparse optimization
• Lagrangian method
• iterative hard thresholding method
• compressed sensing
• sparse logistic regression