An Algorithm for Quadratic ℓ1-Regularized Optimization with a Flexible Active-Set Strategy

We present an active-set method for minimizing an objective that is the sum of a convex quadratic and ℓ1 regularization term. Unlike two-phase methods that combine a first-order active set identification step and a subspace phase consisting of a cycle of conjugate gradient iterations, the method presented here has the flexibility of computing one of three possible steps at each iteration: a relaxation step (that releases variables from the active set), a subspace minimization step based on the conjugate gradient iteration, and an active-set refinement step. The choice of step depends on the relative magnitudes of the components of the minimum norm subgradient. The paper establishes global rates of convergence, as well as work complexity estimates. Numerical results illustrating the behavior of the methods on four test sets are presented.