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 (2018), pp. 1842-1866] that solves these problems by using the bisection method to find a root of a univariate nonsmooth equation phi(lambda ) = (sic) for some (sic) > 0, where phi(center dot) 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, phi(center dot) is piecewise C-k in an open interval containing the solution lambda* to the equation phi(lambda ) = (sic) and that (ii) the Clarke Jacobian of phi(center dot) 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 phi(center dot). The high efficiency of the proposed algorithm is demonstrated by extensive numerical results.