Fast alternating linearization methods for minimizing the sum of two convex functions
From MaRDI portal
algorithmalternating direction methodalternating linearization methodaugmented Langrangian methodconvergenceconvex optimizationGauss-Seidel methoditeration complexity boundslarge-scale problemsLipschitz constantLipschitz continuous gradientmaximal monotone operatorsnumerical resultsoptimal gradient methodPeaceman-Rachford methodsubgradientvariable 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.
The authors propose the following convex optimization problem: (1) \(\min_{x \in \mathbb R^n} F(x) \equiv f(x) + g(x)\), where \((f,g):\mathbb R^n \rightarrow \mathbb R\) are both convex functions such that two problems are easy to solve for any \(\mu >0\) and \(z \in \mathbb R^n\) relative to minimizing \(F(x)\): (2) \(\min_{x \in \mathbb R^n} \{f(x) + \frac{1}{2\mu}\|x-z\|^2\}\) and (3) \(\min_{x \in \mathbb R^n} \{g(x) + \frac{1}{2\mu}\|x-z\|^2\}\) where \(f(.)\) (\(g(.)\), resp.) is a function of a matrix \(X \in \mathbb R^{m\times n}\). Problem (2) ((3), resp.) is associated with a matrix \(Z \in \mathbb R^{m \times n}\) instead of \(z \in \mathbb R^n\) and the \(\|. \|\) norm is the Frobenius norm. For large-scale problems, the class of alternating direction methods that are based on a variable splitting combined with the augmented Lagrangian method are particularly important. In these methods, one splits the variable \(x\) into two variables, i.e., one introduces a new variable \(y\) and rewrites Problem (1) as (4) \(\min \{ f(x) + g(y): x-y = 0\). Since problem (4) is an equality constrained problem, the augmented Lagrangian method can be used to solve it. Another important and related class of algorithms for solving (1) is based on operator splitting. The aim of these algorithms is to find an \(x\) such that \(0 \in T_1 (x) + T_2 (x)\), where \(T_1\) and \(T_2\) are maximal monotone operators. This is a more general problem than (1). Main result: The global convergence results for various splitting and alternating direction algorithms are established under appropriate conditions, the authors' interest here is on iteration complexity bounds for such algorithms. Finally, numerical results are proposed. These results demonstrate the efficiency and the practical potential of authors' 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
- 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 Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- 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 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
- An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems
- An EM algorithm for wavelet-based image restoration
- 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 first-order methods for composite convex optimization with backtracking
- Fast Image Recovery Using Variable Splitting and Constrained Optimization
- Fast multiple-splitting algorithms for convex optimization
- Fixed point and Bregman iterative methods for matrix rank minimization
- Fixed-Point Continuation for \ell₁-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
- 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?)
- 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
(77)- Stochastic accelerated alternating direction method of multipliers with importance sampling
- Accelerated alternating descent methods for Dykstra-like problems
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- A nonmonotone gradient algorithm for total variation image denoising problems
- ROML: a robust feature correspondence approach for matching objects in a set of images
- Accelerated linearized Bregman method
- Iterative adaptive nonconvex low-rank tensor approximation to image restoration based on ADMM
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- Selective linearization for multi-block statistical learning
- An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information
- Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
- An ADMM-based SQP method for separably smooth nonconvex optimization
- A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization
- Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
- A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
- Manifold regularized matrix completion for multi-label learning with ADMM
- Robust PCA using nonconvex rank approximation and sparse regularizer
- Efficient iterative solution of finite element discretized nonsmooth minimization problems
- Robust principal component analysis using facial reduction
- A QCQP-based splitting SQP algorithm for two-block nonconvex constrained optimization problems with application
- A linearized Peaceman-Rachford splitting method for structured convex optimization with application to stable principal component pursuit
- Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
- An alternating direction method of multipliers for tensor complementarity problems
- Semisupervised data classification via the Mumford-Shah-Potts-type model
- A class of alternating linearization algorithms for nonsmooth convex optimization
- Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
- On the global and linear convergence of the generalized alternating direction method of multipliers
- Alternating proximal gradient method for convex minimization
- LAVIR -- locally adaptive variational image registration
- Fast bundle-level methods for unconstrained and ball-constrained convex optimization
- Efficient algorithms for robust and stable principal component pursuit problems
- Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming
- A proximal multiplier method for separable convex minimization
- Fast multiple-splitting algorithms for convex optimization
- Multiplicative noise removal combining a total variation regularizer and a nonconvex regularizer
- Distributed solutions for loosely coupled feasibility problems using proximal splitting methods
- A survey on operator splitting and decomposition of convex programs
- Convergence rate of a proximal multiplier algorithm for separable convex minimization
- Complexity Certification of the Fast Alternating Minimization Algorithm for Linear MPC
- An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing
- On the Use of ADMM for Imaging Inverse Problems: the Pros and Cons of Matrix Inversions
- A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
- Fast first-order methods for composite convex optimization with backtracking
- Alternating direction method of multipliers for sparse principal component analysis
- Proximal Decomposition Via Alternating Linearization
- Proximal-based pre-correction decomposition methods for structured convex minimization problems
- An alternating direction method with increasing penalty for stable principal component pursuit
- Fast algorithm for color texture image inpainting using the non-local CTV model
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- scientific article; zbMATH DE number 7363383 (Why is no real title available?)
- Least-squares approach to risk parity in portfolio selection
- A new homotopy proximal variable-metric framework for composite convex minimization
- Alternating minimization algorithm for minimizing the sum of strongly convex function and weakly convex function
- On the linear convergence of the alternating direction method of multipliers
- Adaptive smoothing algorithms for nonsmooth composite convex minimization
- An accelerated linearized alternating direction method of multipliers
- An extragradient-based alternating direction method for convex minimization
- A new convergence analysis and perturbation resilience of some accelerated proximal forward-backward algorithms with errors
- Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection
- IMRO: A proximal quasi-Newton method for solving _1-regularized least squares problems
- A fast method for obtaining convex combination coefficients
- A proximal bundle method for a class of nonconvex nonsmooth composite optimization problems
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Solving variational inequalities and cone complementarity problems in nonsmooth dynamics using the alternating direction method of multipliers
- A variational model for cartoon-texture decomposition of a color image
- Nonparametric Finite Mixture of Gaussian Graphical Models
- The exact worst-case convergence rate of the alternating direction method of multipliers
- Revisiting parallel splitting augmented Lagrangian method: tight convergence and ergodic convergence rate
- Inertial alternating direction method of multipliers with logarithmic-quadratic proximal regularization
- A symmetric primal-dual method with double extrapolation for composite convex optimization involving three functions
- Accelerated linearized alternating direction method of multipliers with Nesterov extrapolation
- Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems
- An alternating linearization bundle method for a class of nonconvex nonsmooth optimization problems
- A proximal alternating linearization method for minimizing the sum of two convex functions
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis
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)
