Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods

DOI10.1007/S10107-011-0484-9zbMath1260.49048OpenAlexW1967138577MaRDI QIDQ1942265

Jérôme Bolte, Hedy Attouch, Benar Fux Svaiter

Publication date: 18 March 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-011-0484-9

zbMATH Keywords

relative error descent methods sufficient decrease forward-backward splitting nonconvex nonsmooth optimization Kurdyka-Łojasiewicz inequality o-minimal structures proximal algorithms alternating minimization iterative thresholding block-coordinate methods semi-algebraic optimization tame optimization

Mathematics Subject Classification ID

Convex programming (90C25) Newton-type methods (49M15) Methods of quasi-Newton type (90C53) Variational methods involving nonlinear operators (47J30) Iterative procedures involving nonlinear operators (47J25) Numerical methods based on nonlinear programming (49M37) Evolution inclusions (34G25) Nonlinear evolution equations (47J35) Numerical methods for variational inequalities and related problems (65K15)

Related Items (only showing first 100 items - show all)

Two-Phase Image Segmentation by Nonconvex Nonsmooth Models with Convergent Alternating Minimization Algorithms ⋮ On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error ⋮ A Unified Analysis of Descent Sequences in Weakly Convex Optimization, Including Convergence Rates for Bundle Methods ⋮ A Global Convergence Analysis for Computing a Symmetric Low-Rank Orthogonal Approximation ⋮ Zeroth-order optimization with orthogonal random directions ⋮ Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations ⋮ Half-quadratic alternating direction method of multipliers for robust orthogonal tensor approximation ⋮ A converged deep graph semi-NMF algorithm for learning data representation ⋮ On an iteratively reweighted linesearch based algorithm for nonconvex composite optimization ⋮ An extrapolated iteratively reweighted $\ell_1$ method with complexity analysis ⋮ Error bounds, facial residual functions and applications to the exponential cone ⋮ A trust-region LP-Newton method for constrained nonsmooth equations under Hölder metric subregularity ⋮ A gradient sampling algorithm for stratified maps with applications to topological data analysis ⋮ Global convergence of the gradient method for functions definable in o-minimal structures ⋮ Dynamic string‐averaging CQ‐methods for the split feasibility problem with percentage violation constraints arising in radiation therapy treatment planning ⋮ A proximal alternating minimization algorithm for the largest C-eigenvalue of piezoelectric-type tensors ⋮ Some accelerated alternating proximal gradient algorithms for a class of nonconvex nonsmooth problems ⋮ Convergence of the Momentum Method for Semialgebraic Functions with Locally Lipschitz Gradients ⋮ Convergence Analysis of the Proximal Gradient Method in the Presence of the Kurdyka–Łojasiewicz Property Without Global Lipschitz Assumptions ⋮ Fully-connected tensor network decomposition for robust tensor completion problem ⋮ Preconditioned Algorithm for Difference of Convex Functions with Applications to Graph Ginzburg–Landau Model ⋮ Doubly iteratively reweighted algorithm for constrained compressed sensing models ⋮ Coercivity and generalized proximal algorithms: application -- traveling around the world ⋮ A generalized inertial proximal alternating linearized minimization method for nonconvex nonsmooth problems ⋮ A convergent iterative support shrinking algorithm for non-Lipschitz multi-phase image labeling model ⋮ Impulse noise removal by using a nonconvex TGV regularizer and nonconvex fidelity ⋮ A framelet sparse reconstruction method for pansharpening with guaranteed convergence ⋮ A Regularized Newton Method for ${\boldsymbol{\ell}}_{q}$ -Norm Composite Optimization Problems ⋮ Tensor factorization via transformed tensor-tensor product for image alignment ⋮ A comparison of edge-preserving approaches for differential interference contrast microscopy ⋮ A generalized non-convex method for robust tensor completion ⋮ Non-convex fractional-order derivative for single image blind restoration ⋮ Convergence rate analysis of an extrapolated proximal difference-of-convex algorithm ⋮ Sequential Model Correction for Nonlinear Inverse Problems ⋮ Inertial Newton algorithms avoiding strict saddle points ⋮ A class of modified accelerated proximal gradient methods for nonsmooth and nonconvex minimization problems ⋮ First order inertial optimization algorithms with threshold effects associated with dry friction ⋮ On the relationship between the Kurdyka-Łojasiewicz property and error bounds on Hadamard manifolds ⋮ Image cartoon-texture decomposition by a generalized non-convex low-rank minimization method ⋮ A singular value shrinkage thresholding algorithm for folded concave penalized low-rank matrix optimization problems ⋮ Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems ⋮ Convergence of a Class of Nonmonotone Descent Methods for Kurdyka–Łojasiewicz Optimization Problems ⋮ Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for $\boldsymbol{\ell_1}$ -Norm Principal Component Analysis ⋮ On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization ⋮ A line search based proximal stochastic gradient algorithm with dynamical variance reduction ⋮ A refined inertial DC algorithm for DC programming ⋮ A Unified View of Exact Continuous Penalties for $\ell_2$-$\ell_0$ Minimization ⋮ Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality ⋮ Inducing sparsity via the horseshoe prior in imaging problems ⋮ Conservative parametric optimality and the ridge method for tame min-max problems ⋮ A forward-backward algorithm with different inertial terms for structured non-convex minimization problems ⋮ An alternating structure-adapted Bregman proximal gradient descent algorithm for constrained nonconvex nonsmooth optimization problems and its inertial variant ⋮ Calculus rules of the generalized concave Kurdyka-Łojasiewicz property ⋮ Provable Phase Retrieval with Mirror Descent ⋮ A Learnable Group-Tube Transform Induced Tensor Nuclear Norm and Its Application for Tensor Completion ⋮ The Variable Metric Forward-Backward Splitting Algorithm Under Mild Differentiability Assumptions ⋮ Unnamed Item ⋮ Alternating Proximal Regularized Dictionary Learning ⋮ A nonconvex ADMM for a class of sparse inverse semidefinite quadratic programming problems ⋮ Multiplicative Noise Removal: Nonlocal Low-Rank Model and Its Proximal Alternating Reweighted Minimization Algorithm ⋮ The Epsilon-Alternating Least Squares for Orthogonal Low-Rank Tensor Approximation and Its Global Convergence ⋮ A globally convergent algorithm for a class of gradient compounded non-Lipschitz models applied to non-additive noise removal ⋮ An introduction to continuous optimization for imaging ⋮ Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results ⋮ ADMM for multiaffine constrained optimization ⋮ A second-order dynamical approach with variable damping to nonconvex smooth minimization ⋮ On phase retrieval via matrix completion and the estimation of low rank PSD matrices ⋮ Spectral Operators of Matrices: Semismoothness and Characterizations of the Generalized Jacobian ⋮ Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence ⋮ On Algorithms for Difference of Monotone Operators ⋮ On Algorithms for Difference of Monotone Operators ⋮ The Boosted Difference of Convex Functions Algorithm for Nonsmooth Functions ⋮ A nonconvex penalization algorithm with automatic choice of the regularization parameter in sparse imaging ⋮ Composite Optimization by Nonconvex Majorization-Minimization ⋮ Modern regularization methods for inverse problems ⋮ A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems ⋮ Alternating Structure-Adapted Proximal Gradient Descent for Nonconvex Nonsmooth Block-Regularized Problems ⋮ Hessian Barrier Algorithms for Linearly Constrained Optimization Problems ⋮ Scalable Bayesian Uncertainty Quantification in Imaging Inverse Problems via Convex Optimization ⋮ Non-Lipschitz Models for Image Restoration with Impulse Noise Removal ⋮ Matrix completion via minimizing an approximate rank ⋮ Accelerate stochastic subgradient method by leveraging local growth condition ⋮ Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs ⋮ Proximal Heterogeneous Block Implicit-Explicit Method and Application to Blind Ptychographic Diffraction Imaging ⋮ Luminance-Chrominance Model for Image Colorization ⋮ The Primal-Dual Hybrid Gradient Method for Semiconvex Splittings ⋮ A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima ⋮ Nonlocal robust tensor recovery with nonconvex regularization ^* ⋮ Approximate first-order primal-dual algorithms for saddle point problems ⋮ Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences ⋮ Choose Your Path Wisely: Gradient Descent in a Bregman Distance Framework ⋮ Learnable Descent Algorithm for Nonsmooth Nonconvex Image Reconstruction ⋮ A partially inexact ADMM with o(1/n) asymptotic convergence rate, 𝒪(1/n) complexity, and immediate relative error tolerance ⋮ Robust Tensor Completion: Equivalent Surrogates, Error Bounds, and Algorithms ⋮ Sparse Solutions of a Class of Constrained Optimization Problems ⋮ On Optimality Conditions for Nonlinear Conic Programming ⋮ Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs ⋮ Bregman Finito/MISO for Nonconvex Regularized Finite Sum Minimization without Lipschitz Gradient Continuity ⋮ Examples of Pathological Dynamics of the Subgradient Method for Lipschitz Path-Differentiable Functions ⋮ An inertial proximal alternating direction method of multipliers for nonconvex optimization

Cites Work

This page was built for publication: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods