EFFICIENT SPARSE HESSIAN-BASED SEMISMOOTH NEWTON ALGORITHMS FOR DANTZIG SELECTOR\ast

This paper focuses on efficient algorithms for finding the Dantzig selector which was first proposed by Cande`\s and Tao as an effective variable selection technique in the linear regression. This paper first reformulates the Dantzig selector problem as an equivalent convex composite optimization problem and proposes a semismooth Newton augmented Lagrangian (SSNAL) algorithm to solve the equivalent form. This paper also applies a proximal point dual semismooth Newton (PPDSSN) algorithm to solve another equivalent form of the Dantzig selector problem. Comprehensive results on the global convergence and local asymptotic superlinear convergence of the SSNAL and PPDSSN algorithms are characterized under very mild conditions. The computational costs of a semismooth Newton algorithm for solving the subproblems involved in the SSNAL and PPDSSN algorithms can be cheap by fully exploiting the second order sparsity and employing efficient techniques. Numerical experiments on the Dantzig selector problem with synthetic and real data sets demonstrate that the SSNAL and PPDSSN algorithms substantially outperform the state-of-the-art first order algorithms even for the required low accuracy, and the proposed algorithms are able to solve the large-scale problems robustly and efficiently to a relatively high accuracy.

Automated summary

This paper introduces efficient algorithms for solving the Dantzig selector problem, which demonstrate global and local convergence under mild conditions, along with reduced computational costs by utilizing second order sparsity and efficient techniques.