On resolution of L1-norm minimization via a two-metric adaptive projection method

The two-metric projection method is a simple yet elegant algorithm proposed by Bertsekas to address bound/box-constrained optimization problems. The algorithm's low per-iteration cost and potential for using Hessian information make it a favorable computation method for this problem class. Inspired by this algorithm, we propose a two-metric adaptive projection method for solving the $\ell_1$-norm regularization problem that inherits these advantages. We demonstrate that the method is theoretically sound - it has global convergence. Furthermore, it is capable of manifold identification and has superlinear convergence rate under the error bound condition and strict complementarity. Therefore, given sparsity in the solution, the method enjoys superfast convergence in iteration while maintaining scalability, making it desirable for large-scale problems. We also equip the algorithm with competitive complexity to solve nonconvex problems. Numerical experiments are conducted to illustrate the advantages of this algorithm implied by the theory compared to other competitive methods, especially in large-scale scenarios. In contrast to the original two-metric projection method, our algorithm directly solves the $\ell_1$-norm minimization problem without resorting to the intermediate reformulation as a bound-constrained problem, so it circumvents the issue of numerical instability.