Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates

DOI10.1007/s10957-014-0642-3zbMath1316.49039arXiv1405.1357OpenAlexW2004160833MaRDI QIDQ2349844

Pierre Frankel, Juan Peypouquet, Guillaume Garrigos

Publication date: 18 June 2015

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

convergence ratesNewton-like methodGauss-Seidel methoddescent methodsvariable metricKurdyka-Łojasiewicz inequalitynonconvex and nonsmooth optimization

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Numerical optimization and variational techniques (65K10) Newton-type methods (49M15) Numerical methods based on nonlinear programming (49M37)

Related Items

Convergence rate analysis for the higher order power method in best rank one approximations of tensors, Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes, An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions, Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems, A survey on some recent developments of alternating direction method of multipliers, Local convergence of the heavy-ball method and iPiano for non-convex optimization, A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function, Global convergence of model function based Bregman proximal minimization algorithms, Approaching nonsmooth nonconvex optimization problems through first order dynamical systems with hidden acceleration and Hessian driven damping terms, A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem, An inertial Tseng's type proximal algorithm for nonsmooth and nonconvex optimization problems, Kurdyka-Łojasiewicz exponent via inf-projection, New convergence results for the inexact variable metric forward-backward method, Backward-forward algorithms for structured monotone inclusions in Hilbert spaces, From error bounds to the complexity of first-order descent methods for convex functions, A gradient-type algorithm with backward inertial steps associated to a nonconvex minimization problem, Forward-Backward Envelope for the Sum of Two Nonconvex Functions: Further Properties and Nonmonotone Linesearch Algorithms, On an iteratively reweighted linesearch based algorithm for nonconvex composite optimization, An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis, The convergence properties of infeasible inexact proximal alternating linearized minimization, Serial and parallel approaches for image segmentation by numerical minimization of a second-order functional, Thresholding gradient methods in Hilbert spaces: support identification and linear convergence, A comparison of edge-preserving approaches for differential interference contrast microscopy, A class of modified accelerated proximal gradient methods for nonsmooth and nonconvex minimization problems, Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for \(\boldsymbol{\ell_1}\) -Norm Principal Component Analysis, Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry, An accelerated proximal algorithm for regularized nonconvex and nonsmooth bi-level optimization, Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality, A forward-backward algorithm with different inertial terms for structured non-convex minimization problems, The operator splitting schemes revisited: primal-dual gap and degeneracy reduction by a unified analysis, Proximal gradient method with extrapolation and line search for a class of non-convex and non-smooth problems, Template-based image reconstruction facing different topologies, Convergence Analysis for Bregman Iterations in Minimizing a Class of Landau Free Energy Functionals, Analysis of a variable metric block coordinate method under proximal errors, The Variable Metric Forward-Backward Splitting Algorithm Under Mild Differentiability Assumptions, A proximal interior point algorithm with applications to image processing, The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates, An abstract convergence framework with application to inertial inexact forward-backward methods, General descent method using w-distance. Application to emergence of habits following worthwhile moves, Convergence of Inexact Forward--Backward Algorithms Using the Forward--Backward Envelope, Unifying Abstract Inexact Convergence Theorems and Block Coordinate Variable Metric iPiano, Variable metric techniques for forward-backward methods in imaging, The Kurdyka–Łojasiewicz Inequality as Regularity Condition, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, Local Minimizers of Semi-Algebraic Functions from the Viewpoint of Tangencies, A generalized inexact proximal point method for nonsmooth functions that satisfies Kurdyka Łojasiewicz inequality, Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization, On the proximal gradient algorithm with alternated inertia, Convergence of iterative hard-thresholding algorithm with continuation, Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions, Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems, Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems, Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods, A block coordinate variable metric forward-backward algorithm, Proximal algorithms in statistics and machine learning, A block coordinate variable metric linesearch based proximal gradient method, Variable Metric Inexact Line-Search-Based Methods for Nonsmooth Optimization, Sharpness, Restart, and Acceleration, Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method, A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization, A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions, Greedy approximate projection for magnetic resonance fingerprinting with partial volumes, A variational proximal alternating linearized minimization in a given metric for limited-angle CT image reconstruction, Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints, An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems, A regularized alternating direction method of multipliers for a class of nonconvex problems, Sequence Convergence of Inexact Nonconvex and Nonsmooth Algorithms with More Realistic Assumptions, Adaptive FISTA for Nonconvex Optimization, Variable Metric Forward-Backward Algorithm for Composite Minimization Problems, Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs, Proximal gradient method for nonconvex and nonsmooth optimization on Hadamard manifolds, On a general smoothly truncated regularization for variational piecewise constant image restoration: construction and convergent algorithms, Proximal Heterogeneous Block Implicit-Explicit Method and Application to Blind Ptychographic Diffraction Imaging, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, Convergence to equilibrium for time and space discretizations of the Cahn-Hilliard equation, Learnable Descent Algorithm for Nonsmooth Nonconvex Image Reconstruction, Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs, Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem, Proximal Gradient Methods for Machine Learning and Imaging, Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis, Restarting Frank-Wolfe: faster rates under Hölderian error bounds

Uses Software

• iPiano

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
• The Łojasiewicz gradient inequality in the infinite-dimensional Hilbert space framework
• Approximation of sparse controls in semilinear equations by piecewise linear functions
• A block coordinate variable metric forward-backward algorithm
• Asymptotics for a class of non-linear evolution equations, with applications to geometric problems
• Local linear convergence for alternating and averaged nonconvex projections
• Convergence and decay rate to equilibrium of bounded solutions of quasilinear parabolic equations
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• Convergence to equilibrium for the backward Euler scheme and applications
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• Finite termination of the proximal point algorithm
• Produits infinis de resolvantes
• Convergence of solutions to second-order gradient-like systems with analytic nonlinearities
• On gradients of functions definable in o-minimal structures
• On semi- and subanalytic geometry
• Convergence to steady states in asymptotically autonomous semilinear evolution equations.
• Geometric categories and o-minimal structures
• 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
• Counting the faces of randomly-projected hypercubes and orthants, with applications
• Constructive solution of a bilinear optimal control problem for a Schrödinger equation
• A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion
• iPiano: Inertial Proximal Algorithm for Nonconvex Optimization
• A proximal alternating linearization method for nonconvex optimization problems
• A Continuous Dynamical Newton-Like Approach to Solving Monotone Inclusions
• Rank-Sparsity Incoherence for Matrix Decomposition
• Interior proximal algorithm with variable metric for second-order cone programming: applications to structural optimization and support vector machines
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Two-Metric Projection Methods for Constrained Optimization
• Clarke Subgradients of Stratifiable Functions
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Monotone Operators and the Proximal Point Algorithm
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• Hessian Riemannian Gradient Flows in Convex Programming
• Projected Newton Methods for Optimization Problems with Simple Constraints
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Convergence of the Iterates of Descent Methods for Analytic Cost Functions
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Convergence in gradient-like systems which are asymptotically autonomous and analytic