Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs

Abstract

In this paper, we consider a broad class of nonsmooth and nonconvex fractional programs, where the numerator can be written as the sum of a continuously differentiable convex function whose gradient is Lipschitz continuous and a proper lower semicontinuous (possibly nonconvex) function, and the denominator is weakly convex over the constraint set. This model problem includes the composite optimization problems studied extensively lately, and encompasses many important modern fractional optimization problems arising from diverse areas such as the recently proposed scale invariant sparse signal reconstruction problem in signal processing. We propose a proximal subgradient algorithm with extrapolations for solving this optimization model and show that the iterated sequence generated by the algorithm is bounded and any of its limit points is a stationary point of the model problem. The choice of our extrapolation parameter is flexible and includes the popular extrapolation parameter adopted in the restarted Fast Iterative Shrinking-Threshold Algorithm (FISTA). By providing a unified analysis framework of descent methods, we establish the convergence of the full sequence under the assumption that a suitable merit function satisfies the Kurdyka--Łojasiewicz (KL) property. In particular, our algorithm exhibits linear convergence for the scale invariant sparse signal reconstruction problem and the Rayleigh quotient problem over spherical constraint. In the case where the denominator is the maximum of finitely many continuously differentiable weakly convex functions, we also propose an enhanced extrapolated proximal subgradient algorithm with guaranteed convergence to a stronger notion of stationary points of the model problem. Finally, we illustrate the proposed methods by both analytical and simulated numerical examples.

Revised version: Oct. 16, 2020

References in corpus (2)

• iPiano: Inertial Proximal Algorithm for Non-Convex Optimization
• Analysis and algorithms for some compressed sensing models based on L1/L2 minimization

Cited by in corpus (10)

• A structured L-BFGS method and its application to inverse problems
• Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems
• Bregman Proximal Linearized ADMM for Minimizing Separable Sums Coupled by a Difference of Functions
• A proximal subgradient algorithm with extrapolation for structured nonconvex nonsmooth problems
• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points
• Fast Gradient Algorithm with Dry-like Friction and Nonmonotone Line Search for Nonconvex Optimization Problems
• Doubly relaxed forward-Douglas--Rachford splitting for the sum of two nonconvex and a DC function
• Minimization of the $q$-ratio sparsity with $1<q\le \infty$ for signal recovery
• Analysis of The Ratio of ${\ell }_1$ and ${\ell }_2$ Norms in Compressed Sensing
• A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness