IEEE Access (Jan 2018)
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