Fast alternating linearization methods for minimizing the sum of two convex functions
From MaRDI portal
convergenceconvex optimizationnumerical resultsalgorithmoptimal gradient methodalternating direction methodmaximal monotone operatorsLipschitz constantGauss-Seidel methodlarge-scale problemssubgradientalternating linearization methodaugmented Langrangian methoditeration complexity boundsLipschitz continuous gradientPeaceman-Rachford methodvariable splitting
Abstract: We present in this paper first-order alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most iterations to obtain an -optimal solution, while our accelerated (i.e., fast) versions of them require at most iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smooth with Lipschitz continuous gradients and one algorithm that needs only one of the functions to be so. Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones proposed by Goldfarb and Ma in [21] where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms.
Recommendations
- A proximal alternating linearization method for minimizing the sum of two convex functions
- A class of alternating linearization algorithms for nonsmooth convex optimization
- Fast multiple-splitting algorithms for convex optimization
- An approximate alternating linearization decomposition method
- Proximal Decomposition Via Alternating Linearization
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 45081 (Why is no real title available?)
- scientific article; zbMATH DE number 6142618 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A family of projective splitting methods for the sum of two maximal monotone operators
- A new inexact alternating directions method for monotone variational inequalities
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
- An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems
- An EM algorithm for wavelet-based image restoration
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- An alternating direction-based contraction method for linearly constrained separable convex programming problems
- Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
- Compressed sensing
- Convergence of fixed-point continuation algorithms for matrix rank minimization
- Exact matrix completion via convex optimization
- Fast Image Recovery Using Variable Splitting and Constrained Optimization
- Fast first-order methods for composite convex optimization with backtracking
- Fast multiple-splitting algorithms for convex optimization
- Fixed point and Bregman iterative methods for matrix rank minimization
- Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
- Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Introductory lectures on convex optimization. A basic course.
- Matrix Completion From a Few Entries
- Model selection and estimation in the Gaussian graphical model
- Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Partial inverse of a monotone operator
- Proximal Decomposition Via Alternating Linearization
- Regularization methods for semidefinite programming
- Robust principal component analysis?
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Signal Recovery by Proximal Forward-Backward Splitting
- Smooth minimization of non-smooth functions
- Solving monotone inclusions via compositions of nonexpansive averaged operators
- Sparse inverse covariance estimation with the graphical lasso
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- The Numerical Solution of Parabolic and Elliptic Differential Equations
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- The Split Bregman Method for L1-Regularized Problems
Cited in
(72)- ROML: a robust feature correspondence approach for matching objects in a set of images
- A proximal alternating linearization method for minimizing the sum of two convex functions
- Manifold regularized matrix completion for multi-label learning with ADMM
- An accelerated linearized alternating direction method of multipliers
- Accelerated alternating descent methods for Dykstra-like problems
- An alternating direction method with increasing penalty for stable principal component pursuit
- Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Fast algorithm for color texture image inpainting using the non-local CTV model
- Alternating direction method of multipliers for sparse principal component analysis
- An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing
- A new convergence analysis and perturbation resilience of some accelerated proximal forward-backward algorithms with errors
- Stochastic accelerated alternating direction method of multipliers with importance sampling
- Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems
- On the linear convergence of the alternating direction method of multipliers
- A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization
- An alternating linearization bundle method for a class of nonconvex nonsmooth optimization problems
- Alternating minimization algorithm for minimizing the sum of strongly convex function and weakly convex function
- Selective linearization for multi-block statistical learning
- An ADMM-based SQP method for separably smooth nonconvex optimization
- An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information
- A linearized Peaceman-Rachford splitting method for structured convex optimization with application to stable principal component pursuit
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
- Fast bundle-level methods for unconstrained and ball-constrained convex optimization
- A QCQP-based splitting SQP algorithm for two-block nonconvex constrained optimization problems with application
- Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Proximal-based pre-correction decomposition methods for structured convex minimization problems
- Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis
- A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
- A proximal bundle method for a class of nonconvex nonsmooth composite optimization problems
- Efficient algorithms for robust and stable principal component pursuit problems
- Convergence rate of a proximal multiplier algorithm for separable convex minimization
- Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
- Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- IMRO: A proximal quasi-Newton method for solving \(\ell_1\)-regularized least squares problems
- Fast first-order methods for composite convex optimization with backtracking
- An alternating direction method of multipliers for tensor complementarity problems
- scientific article; zbMATH DE number 7363383 (Why is no real title available?)
- A proximal multiplier method for separable convex minimization
- A survey on operator splitting and decomposition of convex programs
- Least-squares approach to risk parity in portfolio selection
- Adaptive smoothing algorithms for nonsmooth composite convex minimization
- Fast multiple-splitting algorithms for convex optimization
- An extragradient-based alternating direction method for convex minimization
- A class of alternating linearization algorithms for nonsmooth convex optimization
- Semisupervised data classification via the Mumford-Shah-Potts-type model
- Efficient iterative solution of finite element discretized nonsmooth minimization problems
- A nonmonotone gradient algorithm for total variation image denoising problems
- Robust PCA using nonconvex rank approximation and sparse regularizer
- Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection
- On the global and linear convergence of the generalized alternating direction method of multipliers
- Robust principal component analysis using facial reduction
- Accelerated linearized Bregman method
- Alternating proximal gradient method for convex minimization
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Iterative adaptive nonconvex low-rank tensor approximation to image restoration based on ADMM
- Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
- Nonparametric Finite Mixture of Gaussian Graphical Models
- Solving variational inequalities and cone complementarity problems in nonsmooth dynamics using the alternating direction method of multipliers
- LAVIR -- locally adaptive variational image registration
- A new homotopy proximal variable-metric framework for composite convex minimization
- Distributed solutions for loosely coupled feasibility problems using proximal splitting methods
- The exact worst-case convergence rate of the alternating direction method of multipliers
- A variational model for cartoon-texture decomposition of a color image
- Complexity Certification of the Fast Alternating Minimization Algorithm for Linear MPC
- A fast method for obtaining convex combination coefficients
- On the Use of ADMM for Imaging Inverse Problems: the Pros and Cons of Matrix Inversions
- Multiplicative noise removal combining a total variation regularizer and a nonconvex regularizer
This page was built for publication: Fast alternating linearization methods for minimizing the sum of two convex functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378095)
