A second-order method for convex ₁-regularized optimization with active-set prediction

Abstract

We describe an active-set method for the minimization of an objective function φ that is the sum of a smooth convex function f and an -regularization term. A distinctive feature of the method is the way in which active-set identification and second-order subspace minimization steps are integrated to combine the predictive power of the two approaches. At every iteration, the algorithm selects a candidate set of free and fixed variables, performs an (inexact) subspace phase, and then assesses the quality of the new active set. If it is not judged to be acceptable, then the set of free variables is restricted and a new active-set prediction is made. We establish global convergence for our approach under the assumptions of Lipschitz-continuity and strong-convexity of f, and compare the new method against state-of-the-art codes.

Keywords:

• -minimization
• second-order
• active-set prediction
• active-set correction
• subspace-optimization

AMS Subject Classification:

• 49M
• 65K
• 65H
• 90C

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. Interestingly, the LIBLINEAR website and manual convey that LIBLINEAR is known to perform well on document classification tasks but not necessarily on others.

Additional information

Funding

Authors (N.K. and A.W.) were partially supported by the National Science Foundation grant DMS-1216920. Authors (N.K. and J.N.) were partially supported by National Science Foundation grant DMS-1216567 and Office of Naval Research award N000141410313. Author (F.O.) was supported by the Scientific and Technological Research Council of Turkey grant #113M500 and U.S. Department of Energy Award Number FG02-87ER25047.