SECOND-ORDER ORTHANT-BASED METHODS WITH ENRICHED HESSIAN INFORMATION FOR SPARSE `1–OPTIMIZATION

Abstract. We present a second order algorithm for solving optimization problems involving the sparsity enhancing `1-norm. An orthantwise-direction strategy is used in the spirit of [1]. The main idea of our method consists in computing the descent directions by incorporating second order information both of the regular term and (in weak sense) of the `1-norm. The weak sec-ond order information behind the `1-term is incorporated via a partial Huber regularization. One of the main features of our algorithm consists in a faster identification of the active set. We also prove that our method is equivalent to a semismooth Newton algorithm applied to the optimality condition, under a specific choice of the (SSN) defining constants. We present several computa-tional experiments to show the efficiency of our approach compared to other up-to-date algorithms. 1