First Order Methods Beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems

DOI10.1137/17M1138558zbMath1402.90118arXiv1706.06461MaRDI QIDQ4577742

Yakov Vaisbourd, Jérôme Bolte, Shoham Sabach, Marc Teboulle

Publication date: 3 August 2018

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

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

zbMATH Keywords

global convergence; phase retrieval; Bregman distance; Kurdyka-Łojasiewicz property; semialgebraic functions; proximal gradient algorithms; extended descent lemma; non-Euclidean distances; composite nonconvex nonsmooth minimization; quadratic inverse problems

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C25: Convex programming

52A41: Convex functions and convex programs in convex geometry

49M27: Decomposition methods

26B25: Convexity of real functions of several variables, generalizations

Related Items

Variable Metric Forward-Backward Algorithm for Composite Minimization Problems, Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence Under Bregman Distance Growth Conditions, Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons, Block Bregman Majorization Minimization with Extrapolation, Convex-Concave Backtracking for Inertial Bregman Proximal Gradient Algorithms in Nonconvex Optimization, Optimality Conditions for Minimizers at Infinity in Polynomial Programming, Novel Proximal Gradient Methods for Nonnegative Matrix Factorization with Sparsity Constraints, Efficient Numerical Methods for Computing the Stationary States of Phase Field Crystal Models, Composite Optimization by Nonconvex Majorization-Minimization, Modern regularization methods for inverse problems, A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima, Dual Space Preconditioning for Gradient Descent, On inexact solution of auxiliary problems in tensor methods for convex optimization, Choose Your Path Wisely: Gradient Descent in a Bregman Distance Framework, Bregman proximal gradient algorithms for deep matrix factorization, A simplified view of first order methods for optimization, Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems, A unified convergence analysis of stochastic Bregman proximal gradient and extragradient methods, Quartic first-order methods for low-rank minimization, Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization, Proximal-like incremental aggregated gradient method with Bregman distance in weakly convex optimization problems, A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization, Inexact version of Bregman proximal gradient algorithm, Bregman proximal mappings and Bregman-Moreau envelopes under relative prox-regularity, A telescopic Bregmanian proximal gradient method without the global Lipschitz continuity assumption, On linear convergence of non-Euclidean gradient methods without strong convexity and Lipschitz gradient continuity, General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems, First-order methods almost always avoid strict saddle points

Uses Software

• GESPAR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global convergence of a proximal linearized algorithm for difference of convex functions
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• On gradients of functions definable in o-minimal structures
• Proximal minimization algorithm with \(D\)-functions
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Forward-backward splitting with Bregman distances
• Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• A generalized proximal point algorithm for certain non-convex minimization problems
• Entropic Proximal Mappings with Applications to Nonlinear Programming
• Variational Analysis
• A Generalized Proximal Point Algorithm for the Variational Inequality Problem in a Hilbert Space
• Optical Wavefront Reconstruction: Theory and Numerical Methods
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
• Conditional Gradient Algorithmsfor Rank-One Matrix Approximations with a Sparsity Constraint
• Convex Optimization in Signal Processing and Communications
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Interior Gradient and Proximal Methods for Convex and Conic Optimization
• Signal Recovery by Proximal Forward-Backward Splitting
• A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications