Global convergence of ADMM in nonconvex nonsmooth optimization

DOI10.1007/s10915-018-0757-zzbMath1462.65072arXiv1511.06324OpenAlexW2962853966WikidataQ129719651 ScholiaQ129719651MaRDI QIDQ1736880

Wotao Yin, Jinshan Zeng, Yu Wang

Publication date: 26 March 2019

Published in: Journal of Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

nonconvex optimizationaugmented Lagrangian methodblock coordinate descentalternating direction method of multiplierssparse optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26)

Related Items

High-Dimensional Vector Autoregressive Time Series Modeling via Tensor Decomposition, Two-Phase Image Segmentation by Nonconvex Nonsmooth Models with Convergent Alternating Minimization Algorithms, Sparse Single Index Models for Multivariate Responses, Penalized Quantile Regression for Distributed Big Data Using the Slack Variable Representation, Unnamed Item, An Image Registration Model in Electron Backscatter Diffraction, Minimization of $L_1$ Over $L_2$ for Sparse Signal Recovery with Convergence Guarantee, An extended primal-dual algorithm framework for nonconvex problems: application to image reconstruction in spectral CT, A Splitting Scheme for Flip-Free Distortion Energies, A Unifying Framework for $n$-Dimensional Quasi-Conformal Mappings, Half-quadratic alternating direction method of multipliers for robust orthogonal tensor approximation, A sequential ADMM algorithm to find sparse LCP solutions using a \(l_2-l_1\) regularization technique with application in bimatrix game, Zero-norm regularized problems: equivalent surrogates, proximal MM method and statistical error bound, ALADIN‐—An open‐source MATLAB toolbox for distributed non‐convex optimization, Low-rank tensor data reconstruction and denoising via ADMM: algorithm and convergence analysis, Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact Riemannian submanifold embedded in Euclidean space, Group structure detection for a high‐dimensional panel data model, Hybrid Hard-Soft Screening for High-dimensional Latent Class Analysis, Estimation of banded time-varying precision matrix based on SCAD and group Lasso, Composite optimization with coupling constraints via dual proximal gradient method with applications to asynchronous networks, Drop-DIP: A single-image denoising method based on deep image prior, A Sequential Quadratic Programming Algorithm for Nonsmooth Problems with Upper- \({\boldsymbol{\mathcal{C}^2}}\) Objective, 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, Image segmentation based on the hybrid bias field correction, A new Lagrangian-based first-order method for nonconvex constrained optimization, A real-time identification method of network structure in complex network systems, Complexity analysis of a stochastic variant of generalized alternating direction method of multipliers, Training recurrent neural networks by sequential least squares and the alternating direction method of multipliers, Global Complexity Bound of a Proximal ADMM for Linearly Constrained Nonseparable Nonconvex Composite Programming, Robust time-of-arrival localization via ADMM, A unified surface geometric framework for feature-aware denoising, hole filling and context-aware completion, Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality, Saturation-value based higher-order regularization for color image restoration, On and Beyond Total Variation Regularization in Imaging: The Role of Space Variance, A Flexible Space-Variant Anisotropic Regularization for Image Restoration with Automated Parameter Selection, An Alternating Augmented Lagrangian method for constrained nonconvex optimization, HV geometry for signal comparison, Homogeneity and Sparsity Analysis for High-Dimensional Panel Data Models, An Alternating Direction Method of Multipliers for Inverse Lithography Problem, Synchronous distributed ADMM for consensus convex optimization problems with self-loops, The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates, Relax-and-split method for nonconvex inverse problems, An unbiased approach to compressed sensing, Unnamed Item, 3D Orientation-Preserving Variational Models for Accurate Image Registration, An Algorithm for Second Order Mumford--Shah Models Based on a Taylor Jet Formulation, An ADMM-LAP method for total variation myopic deconvolution of adaptive optics retinal images, Iteratively Reweighted Group Lasso Based on Log-Composite Regularization, A Scale-Invariant Approach for Sparse Signal Recovery, $ \newcommand{\e}{{\rm e}} {\alpha\ell_{1}-\beta\ell_{2}}$ regularization for sparse recovery, Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results, Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold, ADMM for multiaffine constrained optimization, A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems, Consistent Dynamic Mode Decomposition, Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization, Multi-channel Potts-based reconstruction for multi-spectral computed tomography, Limited-Angle CT Reconstruction via the $L_1/L_2$ Minimization, Variational Rician Noise Removal via Splitting on Spheres, Robust Tensor Completion: Equivalent Surrogates, Error Bounds, and Algorithms, New Splitting Algorithms for Multiplicative Noise Removal Based on Aubert-Aujol Model, Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction, 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, Model selection with distributed SCAD penalty, Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization, Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization, Sparsity-aided variational mesh restoration, 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 combined higher order non-convex total variation with overlapping group sparsity for Poisson noise removal, Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms, An Unbiased Approach to Low Rank Recovery, Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints, Bias versus non-convexity in compressed sensing, Nonlinear transform induced tensor nuclear norm for tensor completion, Inertial alternating direction method of multipliers for non-convex non-smooth optimization, 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, Background subtraction with Kronecker-basis-representation based tensor sparsity and \(l_{1,1,2}\) norm, Smoothing strategy along with conjugate gradient algorithm for signal reconstruction, Cauchy noise removal by weighted nuclear norm minimization, Group sparse representation for restoring blurred images with Cauchy noise, Proximal linearization methods for Schatten \(p\)-quasi-norm minimization, Revisiting the redistancing problem using the Hopf-Lax formula, Unnamed Item, A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming, Run-and-inspect method for nonconvex optimization and global optimality bounds for R-local minimizers, Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization, Image restoration via the adaptive \(TV^p\) regularization, Sparsity-regularized skewness estimation for the multivariate skew normal and multivariate skew \(t\) distributions, Unnamed Item, A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems, A penalized nonlinear ADMM algorithm applied to the multi-constrained traffic assignment problem, Alternating direction method of multipliers for nonconvex log total variation image restoration, Image segmentation with depth information via simplified variational level set formulation, Improved Pointwise Iteration-Complexity of A Regularized ADMM and of a Regularized Non-Euclidean HPE Framework, Improved susceptibility artifact correction of echo-planar MRI using the alternating direction method of multipliers, Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes, Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis, Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, A colorization-based anisotropic variational model for vector-valued image compression, Image denoising using combined higher order non-convex total variation with overlapping group sparsity, An overlapping domain decomposition framework without dual formulation for variational imaging problems, A brief introduction to manifold optimization, How can machine learning and optimization help each other better?, Nonconvex optimization for robust tensor completion from grossly sparse observations, 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, Analysis of the alternating direction method of multipliers for nonconvex problems, Feasibility vs. Optimality in Distributed AC OPF: A Case Study Considering ADMM and ALADIN, Acceleration and Global Convergence of a First-Order Primal-Dual Method for Nonconvex Problems, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, Alternating iterative methods for solving tensor equations with applications, Distributed Nash equilibrium seeking under partial-decision information via the alternating direction method of multipliers, Decomposition Methods for Computing Directional Stationary Solutions of a Class of Nonsmooth Nonconvex Optimization Problems, Cauchy noise removal by nonconvex ADMM with convergence guarantees, Fast L1-L2 minimization via a proximal operator, Unnamed Item, The alternating direction method of multipliers for finding the distance between ellipsoids, 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, Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems, Tractable ADMM schemes for computing KKT points and local minimizers for \(\ell_0\)-minimization problems, Nonisometric surface registration via conformal Laplace-Beltrami basis pursuit, Acceleration of primal-dual methods by preconditioning and simple subproblem procedures, Total Variation--Based Phase Retrieval for Poisson Noise Removal, Alternating direction method of multipliers with difference of convex functions, Selective linearization for multi-block statistical learning, Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal, Cauchy noise removal using group-based low-rank prior, Numerical analysis of constrained total variation flows, An extended proximal ADMM algorithm for three-block nonconvex optimization problems, An outer-inner linearization method for non-convex and nondifferentiable composite regularization problems, MAP inference via \(\ell_2\)-sphere linear program reformulation, A new updating method for the damped mass-spring systems, A hybrid Bregman alternating direction method of multipliers for the linearly constrained difference-of-convex problems, An accelerated smoothing gradient method for nonconvex nonsmooth minimization in image processing, Randomized primal-dual proximal block coordinate updates, Block-simultaneous direction method of multipliers: a proximal primal-dual splitting algorithm for nonconvex problems with multiple constraints, Multiscale sparse microcanonical models, LSALSA: accelerated source separation via learned sparse coding, Remove the salt and pepper noise based on the high order total variation and the nuclear norm regularization, Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems, On a general smoothly truncated regularization for variational piecewise constant image restoration: construction and convergent algorithms, Total variation of the normal vector field as shape prior, An inertial proximal partially symmetric ADMM-based algorithm for linearly constrained multi-block nonconvex optimization problems with applications, A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, A Three-Operator Splitting Algorithm for Nonconvex Sparsity Regularization, An adaptive alternating direction method of multipliers, Unnamed Item, Proximal ADMM for nonconvex and nonsmooth optimization, Local saddles of relaxed averaged alternating reflections algorithms on phase retrieval, The Dantzig selector: recovery of signal via ℓ ₁ − αℓ ₂ minimization, Multi-dimensional image recovery via fully-connected tensor network decomposition under the learnable transforms, Solving blind ptychography effectively via linearized alternating direction method of multipliers, Avoiding bad steps in Frank-Wolfe variants, Efficient low-rank regularization-based algorithms combining advanced techniques for solving tensor completion problems with application to color image recovering, Finding the global optimum of a class of quartic minimization problem

Uses Software

• ALGENCAN
• LMaFit
• ARock
• BADMM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A feasible method for optimization with orthogonality constraints
• A splitting method for orthogonality constrained problems
• GAITA: a Gauss-Seidel iterative thresholding algorithm for \(\ell_q\) regularized least squares regression
• An alternating direction algorithm for matrix completion with nonnegative factors
• An augmented Lagrangian approach for sparse principal component analysis
• Characterization of the subdifferential of some matrix norms
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• On semi- and subanalytic geometry
• A new relative perturbation theorem for singular subspaces
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Research on quantum authentication methods for the secure access control among three elements of cloud computing
• Spectral operators of matrices
• Complementary pivot theory of mathematical programming
• Multiplier and gradient methods
• Differences of two semiconvex functions on the real line
• ARock: An Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion
• On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
• Optimization with Sparsity-Inducing Penalties
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• A Singular Value Thresholding Algorithm for Matrix Completion
• Alternating direction methods for classical and ptychographic phase retrieval
• A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds
• Global Convergence of Splitting Methods for Nonconvex Composite Optimization
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• Iteratively reweighted least squares minimization for sparse recovery
• Semismooth and Semiconvex Functions in Constrained Optimization
• Variational Analysis
• Nonconvex Splitting for Regularized Low-Rank + Sparse Decomposition
• <formula formulatype="inline"><tex Notation="TeX">$L_{1/2}$</tex> </formula> Regularization: Convergence of Iterative Half Thresholding Algorithm
• Linear convergence of adaptively iterative thresholding algorithms for compressed sensing
• Parallel Algorithms for Constrained Tensor Factorization via Alternating Direction Method of Multipliers
• Prox-regular functions in variational analysis
• Alternating direction method of multipliers for real and complex polynomial optimization models
• The Primal-Dual Hybrid Gradient Method for Semiconvex Splittings
• Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction
• Self Equivalence of the Alternating Direction Method of Multipliers
• ADMM Algorithmic Regularization Paths for Sparse Statistical Machine Learning
• On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems
• Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Practical Augmented Lagrangian Methods for Constrained Optimization
• Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent