An extragradient-based alternating direction method for convex minimization
From MaRDI portal
Abstract: In this paper, we consider the problem of minimizing the sum of two convex functions subject to linear linking constraints. The classical alternating direction type methods usually assume that the two convex functions have relatively easy proximal mappings. However, many problems arising from statistics, image processing and other fields have the structure that while one of the two functions has easy proximal mapping, the other function is smoothly convex but does not have an easy proximal mapping. Therefore, the classical alternating direction methods cannot be applied. To deal with the difficulty, we propose in this paper an alternating direction method based on extragradients. Under the assumption that the smooth function has a Lipschitz continuous gradient, we prove that the proposed method returns an -optimal solution within iterations. We apply the proposed method to solve a new statistical model called fused logistic regression. Our numerical experiments show that the proposed method performs very well when solving the test problems. We also test the performance of the proposed method through solving the lasso problem arising from statistics and compare the result with several existing efficient solvers for this problem; the results are very encouraging indeed.
Recommendations
- Alternating proximal gradient method for convex minimization
- scientific article; zbMATH DE number 6453672
- Fast alternating linearization methods for minimizing the sum of two convex functions
- A proximal alternating linearization method for minimizing the sum of two convex functions
- A modified alternating direction method for convex minimization problems
Cites work
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 3862940 (Why is no real title available?)
- scientific article; zbMATH DE number 45081 (Why is no real title available?)
- scientific article; zbMATH DE number 3534286 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A New Alternating Minimization Algorithm for Total Variation Image Reconstruction
- A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator
- A new inexact alternating directions method for monotone variational inequalities
- A practical relative error criterion for augmented Lagrangians
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Alternating direction method for covariance selection models
- Alternating direction method of multipliers for sparse principal component analysis
- An alternating extragradient method for total variation-based image restoration from Poisson data
- Application of a Smoothing Technique to Decomposition in Convex Optimization
- Bregmanized nonlocal regularization for deconvolution and sparse reconstruction
- Complexity of Variants of Tseng's Modified F-B Splitting and Korpelevich's Methods for Hemivariational Inequalities with Applications to Saddle-point and Convex Optimization Problems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Fixed point and Bregman iterative methods for matrix rank minimization
- Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
- Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization
- Model selection and estimation in the Gaussian graphical model
- Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data
- New extragradient-type methods for general variational inequalities.
- 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
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
- On the information-adaptive variants of the ADMM: an iteration complexity perspective
- On the sublinear convergence rate of multi-block ADMM
- Parallel coordinate descent methods for big data optimization
- Path-following gradient-based decomposition algorithms for separable convex optimization
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Rank-Sparsity Incoherence for Matrix Decomposition
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
- Robust principal component analysis?
- Smooth minimization of non-smooth functions
- Sparse inverse covariance estimation with the graphical lasso
- Sparsity and Smoothness Via the Fused Lasso
- Split Bregman method for large scale fused Lasso
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- The Numerical Solution of Parabolic and Elliptic Differential Equations
- The Split Bregman Method for L1-Regularized Problems
Cited in
(16)- On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM
- An alternate minimization method beyond positive definite proximal regularization: convergence and complexity
- Iteration-complexity analysis of a generalized alternating direction method of multipliers
- A variational model for cartoon-texture decomposition of a color image
- A double extrapolation primal-dual algorithm for saddle point problems
- On the information-adaptive variants of the ADMM: an iteration complexity perspective
- Pointwise and ergodic convergence rates of a variable metric proximal alternating direction method of multipliers
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error
- A unified convergence analysis of stochastic Bregman proximal gradient and extragradient methods
- Alternating proximal gradient method for convex minimization
- Structure-leveraged methods in breast cancer risk prediction
- Solving convex min-min problems with smoothness and strong convexity in one group of variables and low dimension in the other
- A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- On the pointwise iteration-complexity of a dynamic regularized ADMM with over-relaxation stepsize
This page was built for publication: An extragradient-based alternating direction method for convex minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q525598)
