AN EFFICIENT SIEVING-BASED SECANT METHOD FOR SPARSE OPTIMIZATION PROBLEMS WITH LEAST-SQUARES CONSTRAINTS.

In this paper, we propose an efficient sieving-based secant method to address the computational challenges of solving sparse optimization problems with least-squares constraints. A level-set method has been introduced in [X. Li, D. F. Sun, and K.-C. Toh, SIAM J. Optim., 28 (2018), pp. 1842-1866] that solves these problems by using the bisection method to find a root of a univariate nonsmooth equation varphi (λ) =varrho for some varrho >0, where varphi (·) is the value function computed by a solution of the corresponding regularized least-squares optimization problem. When the objective function in the constrained problem is a polyhedral gauge function, we prove that (i) for any positive integer k, varphi (·) is piecewise Ck in an open interval containing the solution λ ast to the equation varphi (λ) =varrho and that (ii) the Clarke Jacobian of varphi (·) is always positive. These results allow us to establish the essential ingredients of the fast convergence rates of the secant method. Moreover, an adaptive sieving technique is incorporated into the secant method to effectively reduce the dimension of the level-set subproblems for computing the value of varphi (·). The high efficiency of the proposed algorithm is demonstrated by extensive numerical results. [ABSTRACT FROM AUTHOR]