Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems

DOI10.1137/22M1472000zbMATH Open1519.90182arXiv2011.09782MaRDI QIDQ6155872FDOQ6155872

Authors: Radu I. Boţ, Minh N. Dao, G. Li 

Publication date: 7 June 2023

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: In this paper, we consider a class of nonsmooth sum-of-ratios fractional optimization problems with block structure. This model class is ubiquitous and encompasses several important nonsmooth optimization problems in the literature. We first propose an inertial proximal block coordinate method for solving this class of problems by exploiting the underlying structure. The global convergence of our method is guaranteed under the Kurdyka--Lojasiewicz (KL) property and some mild assumptions. We then identify the explicit exponents of the KL property for three important structured fractional optimization problems. In particular, for the sparse generalized eigenvalue problem with either cardinality regularization or sparsity constraint, we show that the KL exponents are 1/2, and so, the proposed method exhibits linear convergence rate. Finally, we illustrate our theoretical results with both analytic and simulated numerical examples.

Full work available at URL: https://arxiv.org/abs/2011.09782

Recommendations

• First-order algorithms for a class of fractional optimization problems
• General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs
• A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems

zbMATH Keywords

sparsitysum-of-ratioslinear convergencefractional programKurdyka-Łojasiewicz propertyproximal block coordinate method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Fractional programming (90C32) Nonconvex programming, global optimization (90C26) Decomposition methods (49M27)

Cites Work

• Variational Analysis
• On Nonlinear Fractional Programming
• Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow
• Sparse Generalized Eigenvalue Problem Via Smooth Optimization
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Restricted normal cones and sparsity optimization with affine constraints
• Title not available (Why is that?)
• On gradients of functions definable in o-minimal structures
• Generalized subdifferentials of the rank function
• On Fréchet subdifferentials
• Fractional Programming. II, On Dinkelbach's Algorithm
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• On the global optimization of sums of linear fractional functions over a convex set
• Fréchet subdifferential calculus and optimality conditions in nondifferentiable programming
• Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint
• Explicit bounds for the Łojasiewicz exponent in the gradient inequality for polynomials
• Alternative branching rules for some nonconvex problems
• An algorithm for generalized fractional programs
• Parametric approaches to fractional programs
• Solving the trust-region subproblem by a generalized eigenvalue problem
• On optimizing the sum of the Rayleigh quotient and the generalized Rayleigh quotient on the unit sphere
• Proximal mapping for symmetric penalty and sparsity
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Proximal-gradient algorithms for fractional programming
• Efficiency of minimizing compositions of convex functions and smooth maps
• Fractional Programming for Communication Systems—Part I: Power Control and Beamforming
• Kurdyka-Łojasiewicz exponent via inf-projection
• Title not available (Why is that?)
• A proximal algorithm with backtracked extrapolation for a class of structured fractional programming
• Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs

Cited In (5)

• A proximal subgradient algorithm with extrapolation for structured nonconvex nonsmooth problems
• Bregman proximal linearized ADMM for minimizing separable sums coupled by a difference of functions
• On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
• Multi-block relaxed-dual linear inertial ADMM algorithm for nonconvex and nonsmooth problems with nonseparable structures
• First-order algorithms for a class of fractional optimization problems

This page was built for publication: Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6155872)