Global Convergence of Splitting Methods for Nonconvex Composite Optimization

DOI10.1137/140998135zbMATH Open1330.90087DBLPjournals/siamjo/LiP15arXiv1407.0753OpenAlexW3105393233WikidataQ57511183 ScholiaQ57511183MaRDI QIDQ3457189FDOQ3457189

G. Li, Ting Kei Pong

Publication date: 11 December 2015

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

Abstract: We consider the problem of minimizing the sum of a smooth function $h$ with a bounded Hessian, and a nonsmooth function. We assume that the latter function is a composition of a proper closed function $P$ and a surjective linear map $calM$, with the proximal mappings of $auP$, $au>0$, simple to compute. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: alternating direction method of multipliers and proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that, if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions $h$ and $P$ are semi-algebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the $el{l}_{1/2}$ regularization. Finally, when $calM$ is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex $h$.

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

zbMATH Keywords

alternating direction method of multipliersglobal convergenceproximal gradient algorithmKurdyka-Łojasiewicz propertynonconvex 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)

Cites Work

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

Cited In (only showing first 100 items - show all)

• A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems
• An alternating direction method of multipliers for the eigenvalue complementarity problem
• A Bregman-style partially symmetric alternating direction method of multipliers for nonconvex multi-block optimization
• Local saddles of relaxed averaged alternating reflections algorithms on phase retrieval
• Limited-Angle CT Reconstruction via the $L_1/L_2$ Minimization
• Weighted hyper-Laplacian prior with overlapping group sparsity for image restoration under Cauchy noise
• A general truncated regularization framework for contrast-preserving variational signal and image restoration: motivation and implementation
• Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence
• On monotone and primal-dual active set schemes for \(\ell^p\)-type problems, \(p \in (0,1]\)
• On polarization-based schemes for the FFT-based computational homogenization of inelastic materials
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Two-Phase Image Segmentation by Nonconvex Nonsmooth Models with Convergent Alternating Minimization Algorithms
• A general system for heuristic minimization of convex functions over non-convex sets
• Robust low-rank kernel multi-view subspace clustering based on the Schatten \(p\)-norm and correntropy
• Whiteness constraints in a unified variational framework for image restoration
• Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
• Fast L1-L2 minimization via a proximal operator
• An ADMM-based SQP method for separably smooth nonconvex optimization
• A regularized alternating direction method of multipliers for a class of nonconvex problems
• A simple effective heuristic for embedded mixed-integer quadratic programming
• Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
• Proximal ADMM for nonconvex and nonsmooth optimization
• Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
• Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
• Global convergence of ADMM in nonconvex nonsmooth optimization
• A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem
• Alternating direction method of multipliers with difference of convex functions
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
• Local convergence of the heavy-ball method and iPiano for non-convex optimization
• Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
• The Primal-Dual Hybrid Gradient Method for Semiconvex Splittings
• Minimization of $L_1$ Over $L_2$ for Sparse Signal Recovery with Convergence Guarantee
• An adaptive alternating direction method of multipliers
• Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure
• Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems
• Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems
• Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
• A General Non-Lipschitz Infimal Convolution Regularized Model: Lower Bound Theory and Algorithm
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems
• Numerical analysis of constrained total variation flows
• Tight Global Linear Convergence Rate Bounds for Operator Splitting Methods
• Optimal Transport Approximation of 2-Dimensional Measures
• A Scale-Invariant Approach for Sparse Signal Recovery
• 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
• Fast algorithms for robust principal component analysis with an upper bound on the rank
• Inexact proximal \(\epsilon\)-subgradient methods for composite convex optimization problems
• Priors with coupled first and second order differences for manifold-valued image processing
• ADMM for multiaffine constrained optimization
• Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems
• The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates
• Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
• Convergence of ADMM for multi-block nonconvex separable optimization models
• Revisiting the redistancing problem using the Hopf-Lax formula
• Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints
• Modern regularization methods for inverse problems
• Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications
• An extended proximal ADMM algorithm for three-block nonconvex optimization problems
• A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization
• Decomposition Methods for Computing Directional Stationary Solutions of a Class of Nonsmooth Nonconvex Optimization Problems
• Title not available (Why is that?)
• Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms
• A nonconvex ADMM for a class of sparse inverse semidefinite quadratic programming problems
• An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration
• Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction
• Robust subspace clustering based on non-convex low-rank approximation and adaptive kernel
• Bregman reweighted alternating minimization and its application to image deblurring
• An inertial proximal alternating direction method of multipliers for nonconvex optimization
• QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
• Nonconvex flexible sparsity regularization: theory and monotone numerical schemes
• A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization
• Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity
• A scale-invariant relaxation in low-rank tensor recovery with an application to tensor completion
• Half-quadratic alternating direction method of multipliers for robust orthogonal tensor approximation
• Low-Complexity Method for Hybrid MPC with Local Guarantees
• Fast and stable nonconvex constrained distributed optimization: the ELLADA algorithm
• Unifying Abstract Inexact Convergence Theorems and Block Coordinate Variable Metric iPiano
• A symmetric splitting sequential quadratic optimization algorithm for two-block nonlinearly constrained nonconvex optimization
• Minimizing L ₁ over L ₂ norms on the gradient
• A Bregman-style improved ADMM and its linearized version in the nonconvex setting: convergence and rate analyses
• Efficient low-rank regularization-based algorithms combining advanced techniques for solving tensor completion problems with application to color image recovering
• Multi-channel Potts-based reconstruction for multi-spectral computed tomography
• Splitting augmented Lagrangian-type algorithms with partial quadratic approximation to solve sparse signal recovery problems
• Convergence of Bregman Peaceman-Rachford splitting method for nonconvex nonseparable optimization
• An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
• On a general smoothly truncated regularization for variational piecewise constant image restoration: construction and convergent algorithms
• An efficient regularized PR splitting type algorithm for two-block nonconvex linear constrained programs in \(\ell_{1 / 2}\) regularized compressed sensing problems
• Proximal linearization methods for Schatten \(p\)-quasi-norm minimization
• Local linear convergence of an ADMM-type splitting framework for equality constrained optimization
• A partial Bregman ADMM with a general relaxation factor for structured nonconvex and nonsmooth optimization
• Sparsity reconstruction using nonconvex TGpV-shearlet regularization and constrained projection
• On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error
• Learning the sparse prior: modern approaches
• An inertial proximal splitting method with applications
• Bregman methods for large-scale optimization with applications in imaging
• On variable splitting and augmented Lagrangian method for total variation-related image restoration models
• A Three-Operator Splitting Algorithm for Nonconvex Sparsity Regularization
• Low-rank matrix recovery problem minimizing a new ratio of two norms approximating the rank function then using an ADMM-type solver with applications
• Title not available (Why is that?)

Uses Software

• RecPF
• BADMM

This page was built for publication: Global Convergence of Splitting Methods for Nonconvex Composite Optimization

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