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 (only showing first 100 items - show all)

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

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

This page was built for publication: Global convergence of ADMM in nonconvex nonsmooth optimization