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

DOI10.1007/s10107-012-0530-2zbMath1280.65051arXiv0912.4571OpenAlexW2010286849WikidataQ101200642 ScholiaQ101200642MaRDI QIDQ378095

Katya Scheinberg, Donald Goldfarb, Shi-Qian Ma

Publication date: 11 November 2013

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

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

zbMATH Keywords

algorithmconvergencemaximal monotone operatorsnumerical resultsconvex optimizationGauss-Seidel methodsubgradientLipschitz constantPeaceman-Rachford methodalternating direction methodlarge-scale problemsalternating linearization methodaugmented Langrangian methoditeration complexity boundsLipschitz continuous gradientoptimal gradient methodvariable splitting

Mathematics Subject Classification ID

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

Related Items

An alternating linearization bundle method for a class of nonconvex nonsmooth optimization problems, Stochastic accelerated alternating direction method of multipliers with importance sampling, An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, 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, A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization, On the global and linear convergence of the generalized alternating direction method of multipliers, Alternating proximal gradient method for convex minimization, Multiplicative noise removal combining a total variation regularizer and a nonconvex regularizer, LAVIR -- locally adaptive variational image registration, Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming, Manifold regularized matrix completion for multi-label learning with ADMM, Distributed solutions for loosely coupled feasibility problems using proximal splitting methods, A new convergence analysis and perturbation resilience of some accelerated proximal forward–backward algorithms with errors, Fast bundle-level methods for unconstrained and ball-constrained convex optimization, A proximal alternating linearization method for minimizing the sum of two convex functions, Fast first-order methods for composite convex optimization with backtracking, Alternating direction augmented Lagrangian methods for semidefinite programming, Unnamed Item, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Robust PCA using nonconvex rank approximation and sparse regularizer, Efficient iterative solution of finite element discretized nonsmooth minimization problems, A proximal bundle method for a class of nonconvex nonsmooth composite optimization problems, Accelerated linearized Bregman method, A survey on operator splitting and decomposition of convex programs, Convergence rate of a proximal multiplier algorithm for separable convex minimization, Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection, Alternating direction method of multipliers for sparse principal component analysis, Robust principal component analysis using facial reduction, Efficient algorithms for robust and stable principal component pursuit problems, On the Use of ADMM for Imaging Inverse Problems: the Pros and Cons of Matrix Inversions, 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, Proximal alternating penalty algorithms for nonsmooth constrained convex optimization, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, 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, An alternating direction method of multipliers for tensor complementarity problems, On the linear convergence of the alternating direction method of multipliers, Adaptive smoothing algorithms for nonsmooth composite convex minimization, Iterative adaptive nonconvex low-rank tensor approximation to image restoration based on ADMM, IMRO: A Proximal Quasi-Newton Method for Solving $\ell_1$-Regularized Least Squares Problems, Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis, A proximal multiplier method for separable convex minimization, 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, A nonmonotone gradient algorithm for total variation image denoising problems, ROML: a robust feature correspondence approach for matching objects in a set of images, Semisupervised data classification via the Mumford-Shah-Potts-type model, Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data, A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization, Accelerated First-Order Primal-Dual Proximal Methods for Linearly Constrained Composite Convex Programming, A class of alternating linearization algorithms for nonsmooth convex optimization, An ADMM-based SQP method for separably smooth nonconvex optimization, Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems, Least-squares approach to risk parity in portfolio selection, A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization, An Accelerated Linearized Alternating Direction Method of Multipliers, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, Mirror Prox algorithm for multi-term composite minimization and semi-separable problems

Uses Software

• glasso
• RecPF

Cites Work

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