AUGMENTED LAGRANGIAN BASED ALGORITHMS FOR CONVEX OPTIMIZATION PROBLEMS WITH NON-SEPARABLE L1-REGULARIZATION

Abstract

We consider the problem of minimizing the sum of a convex function and a non-separable L1-regularization term. The motivation for studying such a class of problems comes from recent interests in various high-dimensional sparse feature learning problems in statistics, as well as from problems in image processing. We propose an inexact semi-smooth Newton augmented Lagrangian (SSNAL) algorithm to solve an equivalent reformulation of the problem, and establish comprehensive results on the global convergence and local rate of convergence of the algorithm. For the purpose of exposition and comparison, we also summarize/design three first-order methods to solve the problem under consideration. Numerical experiments show that the SSNAL algorithm performs favourably in comparison to several state-of-the-art first-order algorithms. In addition, we propose an L1+L2 norm fidelity based minimization model for image restoration problems with mixed or unknown noises. Extensive simulations on synthetic data show that this model is effective and robust in restoring images contaminated by various types of additive and multiplicative noises, as well as their mixtures. Numerical results on real data show that it can remove noises without any prior knowledge of the noise distribution.