Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs
From MaRDI portal
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--{L}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.
Recommendations
- A proximal subgradient algorithm with extrapolation for structured nonconvex nonsmooth problems
- An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems
- Proximal-gradient algorithms for fractional programming
- Proximal bundle algorithms for nonlinearly constrained convex minimax fractional programs
- A proximal algorithm with backtracked extrapolation for a class of structured fractional programming
- Proximal extrapolated gradient methods for variational inequalities
- Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems
- On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems
- Extrapolated smoothing descent algorithm for constrained nonconvex and nonsmooth composite problems
- A proximal point algorithm for generalized fractional programs
Cites work
- scientific article; zbMATH DE number 3848997 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- A Scale-Invariant Approach for Sparse Signal Recovery
- An algorithm for generalized fractional programs
- Analysis and algorithms for some compressed sensing models based on L1/L2 minimization
- Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
- Clarke Subgradients of Stratifiable Functions
- Computing B-stationary points of nonsmooth DC programs
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
- Convex analysis and monotone operator theory in Hilbert spaces
- First-order methods in optimization
- Fractional Programming. II, On Dinkelbach's Algorithm
- Fréchet subdifferential calculus and optimality conditions in nondifferentiable programming
- Introductory lectures on convex optimization. A basic course.
- Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
- On Fréchet subdifferentials
- On Nonlinear Fractional Programming
- On gradients of functions definable in o-minimal structures
- On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
- Parametric approaches to fractional programs
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximal-gradient algorithms for fractional programming
- Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
- Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano
- Using positive spanning sets to achieve d-stationarity with the boosted DC algorithm
- Variational Analysis
- When all risk-adjusted performance measures are the same: in praise of the Sharpe ratio
- iPiano: inertial proximal algorithm for nonconvex optimization
Cited in
(20)- A single-loop proximal subgradient algorithm for A class structured fractional programs
- A structured L-BFGS method and its application to inverse problems
- Doubly relaxed forward-Douglas-Rachford splitting for the sum of two nonconvex and a DC function
- A proximal subgradient algorithm with extrapolation for structured nonconvex nonsmooth problems
- The modified second APG method for a class of nonconvex nonsmooth problems
- Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems
- A Bregman proximal subgradient algorithm for nonconvex and nonsmooth fractional optimization problems
- On Proximal Algorithms with Inertial Effects Beyond Monotonicity
- Calculus rules of the generalized concave Kurdyka-Łojasiewicz property
- Dinkelbach Type Approximation Algorithms for Nonlinear Fractional Optimization Problems
- Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints
- Recovery analysis for the _p/_1 minimization problem
- Componentwise Dinkelbach algorithm for nonlinear fractional optimization problems
- A proximal algorithm with backtracked extrapolation for a class of structured fractional programming
- Bregman proximal linearized ADMM for minimizing separable sums coupled by a difference of functions
- Full splitting algorithms for fractional programs with structured numerators and denominators
- A mirror inertial forward-reflected-backward splitting: convergence analysis beyond convexity and Lipschitz smoothness
- A proximal splitting algorithm for generalized DC programming with applications in signal recovery
- An implementable proximal extragradient method for structured fractional programming
- First-order algorithms for a class of fractional optimization problems
This page was built for publication: Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5868963)
