Retraction-Based First-Order Feasible Methods for Difference-of-Convex Programs with Smooth Inequality and Simple Geometric Constraints

Yongle Zhang, Guoyin Li, Ting Kei Pong, Shiqi Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

In this paper, we propose first-order feasible methods for difference-of-convex (DC) programs with smooth inequality and simple geometric constraints. Our strategy for maintaining feasibility of the iterates is based on a “retraction” idea adapted from the literature of manifold optimization. When the constraints are convex, we establish the global subsequential convergence of the sequence generated by our algorithm under strict feasibility condition, and analyze its convergence rate when the objective is in addition convex according to the Kurdyka-Łojasiewicz (KL) exponent of the extended objective (i.e., sum of the objective and the indicator function of the constraint set). We also show that the extended objective of a large class of Euclidean norm (and more generally, group LASSO penalty) regularized convex optimization problems is a KL function with exponent 12; consequently, our algorithm is locally linearly convergent when applied to these problems. We then extend our method to solve DC programs with a single specially structured nonconvex constraint. Finally, we discuss how our algorithms can be applied to solve two concrete optimization problems, namely, group-structured compressed sensing problems with Gaussian measurement noise and compressed sensing problems with Cauchy measurement noise, and illustrate the empirical performance of our algorithms.

Original languageEnglish
Article number8
Pages (from-to)1-40
Number of pages40
JournalAdvances in Computational Mathematics
Volume49
Issue number1
DOIs
Publication statusPublished - Feb 2023

Keywords

  • Difference-of-convex optimization
  • First-order feasible methods
  • Kurdyka-Łojasiewicz exponents
  • Retraction

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Retraction-Based First-Order Feasible Methods for Difference-of-Convex Programs with Smooth Inequality and Simple Geometric Constraints'. Together they form a unique fingerprint.

Cite this