Fast alternating linearization methods for minimizing the sum of two convex functions

DOI10.1007/S10107-012-0530-2zbMATH Open1280.65051arXiv0912.4571OpenAlexW2010286849WikidataQ101200642 ScholiaQ101200642MaRDI QIDQ378095FDOQ378095

Authors: Donald Goldfarb, Katya Scheinberg, Shiqian Ma 

Publication date: 11 November 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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 $O(1/epsilon)$ iterations to obtain an $epsilon$-optimal solution, while our accelerated (i.e., fast) versions of them require at most $O(1/sqrtepsilon)$ 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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Smooth minimization of non-smooth functions
• Introductory lectures on convex optimization. A basic course.
• Sparse inverse covariance estimation with the graphical lasso
• Robust principal component analysis?
• Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data
• Model selection and estimation in the Gaussian graphical model
• Regularization methods for semidefinite programming
• Exact matrix completion via convex optimization
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The Split Bregman Method for L1-Regularized Problems
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Fast Image Recovery Using Variable Splitting and Constrained Optimization
• An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems
• Compressed sensing
• Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• Signal Recovery by Proximal Forward-Backward Splitting
• Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
• Title not available (Why is that?)
• An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• An EM algorithm for wavelet-based image restoration
• Matrix Completion From a Few Entries
• Fixed point and Bregman iterative methods for matrix rank minimization
• A new inexact alternating directions method for monotone variational inequalities
• A family of projective splitting methods for the sum of two maximal monotone operators
• Title not available (Why is that?)
• Alternating direction augmented Lagrangian methods for semidefinite programming
• An alternating direction-based contraction method for linearly constrained separable convex programming problems
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming
• Partial inverse of a monotone operator
• Convergence of fixed-point continuation algorithms for matrix rank minimization
• Fast multiple-splitting algorithms for convex optimization
• Proximal Decomposition Via Alternating Linearization
• Title not available (Why is that?)
• Fast first-order methods for composite convex optimization with backtracking

Cited In (72)

• 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
• On the Use of ADMM for Imaging Inverse Problems: the Pros and Cons of Matrix Inversions
• A new homotopy proximal variable-metric framework for composite convex minimization
• The exact worst-case convergence rate of the alternating direction method of multipliers
• Distributed solutions for loosely coupled feasibility problems using proximal splitting methods
• Nonparametric Finite Mixture of Gaussian Graphical Models
• LAVIR -- locally adaptive variational image registration
• A fast method for obtaining convex combination coefficients
• Complexity Certification of the Fast Alternating Minimization Algorithm for Linear MPC
• Multiplicative noise removal combining a total variation regularizer and a nonconvex regularizer
• An alternating linearization bundle method for a class of nonconvex nonsmooth optimization problems
• Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
• Robust principal component analysis using facial reduction
• Manifold regularized matrix completion for multi-label learning with ADMM
• Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
• Iterative adaptive nonconvex low-rank tensor approximation to image restoration based on ADMM
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Accelerated linearized Bregman method
• A linearized Peaceman-Rachford splitting method for structured convex optimization with application to stable principal component pursuit
• On the global and linear convergence of the generalized alternating direction method of multipliers
• An ADMM-based SQP method for separably smooth nonconvex optimization
• Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
• A proximal multiplier method for separable convex minimization
• Stochastic accelerated alternating direction method of multipliers with importance sampling
• Least-squares approach to risk parity in portfolio selection
• An accelerated linearized alternating direction method of multipliers
• Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
• Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
• A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem
• Selective linearization for multi-block statistical learning
• An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information
• Fast bundle-level methods for unconstrained and ball-constrained convex optimization
• A class of alternating linearization algorithms for nonsmooth convex optimization
• On the linear convergence of the alternating direction method of multipliers
• Efficient iterative solution of finite element discretized nonsmooth minimization problems
• A survey on operator splitting and decomposition of convex programs
• Alternating proximal gradient method for convex minimization
• A new convergence analysis and perturbation resilience of some accelerated proximal forward-backward algorithms with errors
• A nonmonotone gradient algorithm for total variation image denoising problems
• Efficient algorithms for robust and stable principal component pursuit problems
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• ROML: a robust feature correspondence approach for matching objects in a set of images
• Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems
• A proximal alternating linearization method for minimizing the sum of two convex functions
• Alternating minimization algorithm for minimizing the sum of strongly convex function and weakly convex function
• Proximal-based pre-correction decomposition methods for structured convex minimization problems
• A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
• Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis
• Semisupervised data classification via the Mumford-Shah-Potts-type model
• 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
• Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
• 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
• Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
• Robust PCA using nonconvex rank approximation and sparse regularizer
• Convergence rate of a proximal multiplier algorithm for separable convex minimization
• Fast first-order methods for composite convex optimization with backtracking
• Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection
• A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization
• Title not available (Why is that?)
• Accelerated alternating descent methods for Dykstra-like problems
• A QCQP-based splitting SQP algorithm for two-block nonconvex constrained optimization problems with application
• A proximal bundle method for a class of nonconvex nonsmooth composite optimization problems
• IMRO: A proximal quasi-Newton method for solving \(\ell_1\)-regularized least squares problems
• An alternating direction method of multipliers for tensor complementarity problems
• Fast multiple-splitting algorithms for convex optimization
• Adaptive smoothing algorithms for nonsmooth composite convex minimization
• An extragradient-based alternating direction method for convex minimization
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation

Uses Software

• glasso
• RecPF

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)