Global Convergence of Splitting Methods for Nonconvex Composite Optimization

DOI10.1137/140998135zbMath1330.90087arXiv1407.0753OpenAlexW3105393233WikidataQ57511183 ScholiaQ57511183MaRDI QIDQ3457189

Guoyin Li, Ting Kei Pong

Publication date: 11 December 2015

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

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

zbMATH Keywords

global convergencealternating direction method of multipliersKurdyka-Łojasiewicz propertyproximal gradient algorithmnonconvex composite optimization

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Related Items

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, Half-quadratic alternating direction method of multipliers for robust orthogonal tensor approximation, Low-rank matrix recovery problem minimizing a new ratio of two norms approximating the rank function then using an ADMM-type solver with applications, Convergence analysis of an improved Bregman-type Peaceman-Rachford splitting algorithm for nonconvex nonseparable linearly constrained optimization problems, A Bregman-style partially symmetric alternating direction method of multipliers for nonconvex multi-block optimization, Study on \(L_1\) over \(L_2\) Minimization for nonnegative signal recovery, A symmetric splitting sequential quadratic optimization algorithm for two-block nonlinearly constrained nonconvex optimization, A new Lagrangian-based first-order method for nonconvex constrained optimization, Complexity analysis of a stochastic variant of generalized alternating direction method of multipliers, Convergence of Bregman Peaceman-Rachford splitting method for nonconvex nonseparable optimization, Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality, Optimal Transport Approximation of 2-Dimensional Measures, Unnamed Item, Multi-channel Potts-based reconstruction for multi-spectral computed tomography, Limited-Angle CT Reconstruction via the $L_1/L_2$ Minimization, Choose Your Path Wisely: Gradient Descent in a Bregman Distance Framework, A Global Dual Error Bound and Its Application to the Analysis of Linearly Constrained Nonconvex Optimization, An inertial proximal alternating direction method of multipliers for nonconvex optimization, Weighted hyper-Laplacian prior with overlapping group sparsity for image restoration under Cauchy noise, A General Non-Lipschitz Infimal Convolution Regularized Model: Lower Bound Theory and Algorithm, A survey on some recent developments of alternating direction method of multipliers, Fast and stable nonconvex constrained distributed optimization: the ELLADA algorithm, A dynamic alternating direction of multipliers for nonconvex minimization with nonlinear functional equality constraints, Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms, Local convergence of the heavy-ball method and iPiano for non-convex optimization, An Unbiased Approach to Low Rank Recovery, An inertial Bregman generalized alternating direction method of multipliers for nonconvex optimization, Minimization of $L_1$ Over $L_2$ for Sparse Signal Recovery with Convergence Guarantee, Inertial alternating direction method of multipliers for non-convex non-smooth optimization, Minimizing L ₁ over L ₂ norms on the gradient, Nonconvex flexible sparsity regularization: theory and monotone numerical schemes, Nonconvex and nonsmooth optimization with generalized orthogonality constraints: an approximate augmented Lagrangian method, Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure, Global convergence of unmodified 3-block ADMM for a class of convex minimization problems, Robust subspace clustering based on non-convex low-rank approximation and adaptive kernel, Precompact convergence of the nonconvex primal-dual hybrid gradient algorithm, Low Tucker rank tensor recovery via ADMM based on exact and inexact iteratively reweighted algorithms, A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem, Peaceman-Rachford splitting for a class of nonconvex optimization problems, Proximal linearization methods for Schatten \(p\)-quasi-norm minimization, Convergence of ADMM for multi-block nonconvex separable optimization models, Revisiting the redistancing problem using the Hopf-Lax formula, Dynamic behavior analysis via structured rank minimization, Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization, A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems, Unnamed Item, A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems, A new numerical scheme for discrete constrained total variation flows and its convergence, Robust low-rank kernel multi-view subspace clustering based on the Schatten \(p\)-norm and correntropy, The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates, A two-level distributed algorithm for nonconvex constrained optimization, Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis, A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization, Iterative \(p\)-shrinkage thresholding algorithm for low Tucker rank tensor recovery, An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration, Unifying Abstract Inexact Convergence Theorems and Block Coordinate Variable Metric iPiano, A nonconvex ADMM for a class of sparse inverse semidefinite quadratic programming problems, Bregman reweighted alternating minimization and its application to image deblurring, A QCQP-based splitting SQP algorithm for two-block nonconvex constrained optimization problems with application, An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems, On monotone and primal-dual active set schemes for \(\ell^p\)-type problems, \(p \in (0,1\)], Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, Global convergence of ADMM in nonconvex nonsmooth optimization, A general system for heuristic minimization of convex functions over non-convex sets, Decomposition Methods for Computing Directional Stationary Solutions of a Class of Nonsmooth Nonconvex Optimization Problems, Fast L1-L2 minimization via a proximal operator, Local linear convergence of an ADMM-type splitting framework for equality constrained optimization, A general truncated regularization framework for contrast-preserving variational signal and image restoration: motivation and implementation, Sparsity reconstruction using nonconvex TGpV-shearlet regularization and constrained projection, Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications, Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity, Inexact proximal \(\epsilon\)-subgradient methods for composite convex optimization problems, Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems, Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems, On a monotone scheme for nonconvex nonsmooth optimization with applications to fracture mechanics, 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, Fast algorithms for robust principal component analysis with an upper bound on the rank, Alternating direction method of multipliers with difference of convex functions, A Scale-Invariant Approach for Sparse Signal Recovery, A simple effective heuristic for embedded mixed-integer quadratic programming, Priors with coupled first and second order differences for manifold-valued image processing, Whiteness constraints in a unified variational framework for image restoration, Numerical analysis of constrained total variation flows, An extended proximal ADMM algorithm for three-block nonconvex optimization problems, Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results, ADMM for multiaffine constrained optimization, Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence, MAP inference via \(\ell_2\)-sphere linear program reformulation, A hybrid Bregman alternating direction method of multipliers for the linearly constrained difference-of-convex problems, Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints, An accelerated smoothing gradient method for nonconvex nonsmooth minimization in image processing, Modern regularization methods for inverse problems, A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems, A fundamental proof of convergence of alternating direction method of multipliers for weakly convex optimization, A regularized alternating direction method of multipliers for a class of nonconvex problems, Low-Complexity Method for Hybrid MPC with Local Guarantees, Sequence Convergence of Inexact Nonconvex and Nonsmooth Algorithms with More Realistic Assumptions, An ADMM-based SQP method for separably smooth nonconvex optimization, Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems, An alternating direction method of multipliers for the eigenvalue complementarity problem, On polarization-based schemes for the FFT-based computational homogenization of inelastic materials, On a general smoothly truncated regularization for variational piecewise constant image restoration: construction and convergent algorithms, A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization, A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization, QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs, The Primal-Dual Hybrid Gradient Method for Semiconvex Splittings, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, Two-step inertial Bregman alternating minimization algorithm for nonconvex and nonsmooth problems, A Three-Operator Splitting Algorithm for Nonconvex Sparsity Regularization, An adaptive alternating direction method of multipliers, Proximal ADMM for nonconvex and nonsmooth optimization, Local saddles of relaxed averaged alternating reflections algorithms on phase retrieval, Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction, Efficient low-rank regularization-based algorithms combining advanced techniques for solving tensor completion problems with application to color image recovering, Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons

Uses Software

• RecPF
• BADMM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Iterative thresholding for sparse approximations
• Computing proximal points of nonconvex functions
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• An efficient algorithm for \(\ell_{0}\) minimization in wavelet frame based image restoration
• Eigenvalues of tridiagonal pseudo-Toeplitz matrices
• Minimization of non-smooth, non-convex functionals by iterative thresholding
• On the local convergence of the Douglas-Rachford algorithm
• Exact matrix completion via convex optimization
• Projection Methods: Swiss Army Knives for Solving Feasibility and Best Approximation Problems with Halfspaces
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• Alternating Direction Method for Image Inpainting in Wavelet Domains
• Matrix completion via an alternating direction method
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• A New Alternating Minimization Algorithm for Total Variation Image Reconstruction
• Clarke Subgradients of Stratifiable Functions
• Decoding by Linear Programming
• A generalized proximal point algorithm for certain non-convex minimization problems
• Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
• Variational Analysis
• <formula formulatype="inline"><tex Notation="TeX">$L_{1/2}$</tex> </formula> Regularization: Convergence of Iterative Half Thresholding Algorithm
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems