An efficient sieving-based secant method for sparse optimization problems with least-squares constraints

Abstract

In this paper, we propose an efficient sieving-based secant method to address thecomputational challenges of solving sparse optimization problems with least-squares constraints. Alevel-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 aunivariate nonsmooth equation \varphi (\lambda ) = \varrho for some \varrho > 0, where \varphi (\cdot ) is the value function computed bya solution of the corresponding regularized least-squares optimization problem. When the objectivefunction in the constrained problem is a polyhedral gauge function, we prove that (i) for any positiveinteger k, \varphi (\cdot ) is piecewise Ck in an open interval containing the solution \lambda \ast to the equation \varphi (\lambda ) = \varrho and that (ii) the Clarke Jacobian of \varphi (\cdot ) is always positive. These results allow us to establish theessential ingredients of the fast convergence rates of the secant method. Moreover, an adaptivesieving technique is incorporated into the secant method to effectively reduce the dimension of thelevel-set subproblems for computing the value of \varphi (\cdot ). The high efficiency of the proposed algorithmis demonstrated by extensive numerical results.