An Efficient Sieving-Based Secant Method for Sparse Optimization Problems with Least-Squares Constraints

Qian Li, Defeng Sun, Yancheng Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

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 ϕ(λ)=ρ for some ρ>0, where ϕ(.) 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, ϕ(.) is piecewise CK in an open interval containing the solution λ∗ to the quation ϕ(λ)=ρ and that (ii) the Clarke Jacobian of ϕ(.) 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 ϕ(.) . The high efficiency of the proposed algorithm is demonstrated by extensive numerical results.

Original languageEnglish
Pages (from-to)2038-2066
Number of pages29
JournalSIAM Journal on Optimization
Volume34
Issue number2
DOIs
Publication statusPublished - Jun 2024

Keywords

  • adaptive sieving
  • level-set method
  • secant method
  • semismooth analysis

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'An Efficient Sieving-Based Secant Method for Sparse Optimization Problems with Least-Squares Constraints'. Together they form a unique fingerprint.

Cite this