Fast multiple-splitting algorithms for convex optimization

DOI10.1137/090780705MaRDI QIDQ2910883zbMATH OpenOpenAlexFDO

Authors Donald Goldfarb, Shiqian Ma

Publication date 12 September 2012

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationdecompositionnumerical examplesoptimal gradient methodcomplexity theoryparallel computingproximal point algorithmaugmented Lagrangian methodalternating linearization methodvariable splittingsmoothing techniquesalternating direction

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Complexity and performance of numerical algorithms (65Y20)

Abstract: We present in this paper two different classes of general $K$-splitting algorithms for solving finite-dimensional convex optimization problems. Under the assumption that the function being minimized has a Lipschitz continuous gradient, we prove that the number of iterations needed by the first class of algorithms to obtain an $epsilon$-optimal solution is $O(1/epsilon)$. The algorithms in the second class are accelerated versions of those in the first class, where the complexity result is improved to $O(1/sqrtepsilon)$ while the computational effort required at each iteration is almost unchanged. To the best of our knowledge, the complexity results presented in this paper are the first ones of this type that have been given for splitting and alternating direction type methods. Moreover, all algorithms proposed in this paper are parallelizable, which makes them particularly attractive for solving certain large-scale problems.

Recommendations

• Fast alternating linearization methods for minimizing the sum of two convex functions
• Fast inexact decomposition algorithms for large-scale separable convex optimization
• Some parallel splitting methods for separable convex programming with the \(O(\frac{1}{t})\) convergence rate
• A parallel splitting ALM-based algorithm for separable convex programming
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms

Cited in

(42)

• Inexact alternating direction methods of multipliers for separable convex optimization
• Fast and Effective Multiframe-Task Parameter Assignment Via Concave Approximations of Demand
• Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems
• A linear algebra perspective on the random multi-block ADMM: the QP case
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Accelerated linearized Bregman method
• A simple parallel algorithm with an \(O(1/t)\) convergence rate for general convex programs
• Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning
• On the global and linear convergence of the generalized alternating direction method of multipliers
• Decomposable Markov decision processes: A fluid optimization approach
• Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
• Fast inexact decomposition algorithms for large-scale separable convex optimization
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• Convergence rates for an inexact ADMM applied to separable convex optimization
• Accelerated Bregman operator splitting with backtracking
• An operator-splitting approach for variational optimal control formulations for diffeomorphic shape matching
• A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints
• Two-step fixed-point proximity algorithms for multi-block separable convex problems
• A first-order splitting method for solving a large-scale composite convex optimization problem
• Diffeomorphic shape matching by operator splitting in 3D cardiology imaging
• Block splitting for distributed optimization
• On the linear convergence of the alternating direction method of multipliers
• Some parallel splitting methods for separable convex programming with the \(O(\frac{1}{t})\) convergence rate
• A survey on operator splitting and decomposition of convex programs
• Alternating proximal gradient method for convex minimization
• Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing
• On the Global Linear Convergence of the ADMM with MultiBlock Variables
• Oracle complexity separation in convex optimization
• Accelerating convergence of a class of splitting algorithms with iterative foldings
• iPiasco: inertial proximal algorithm for strongly convex optimization
• Fast alternating linearization methods for minimizing the sum of two convex functions
• 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
• Metric selection in fast dual forward-backward splitting
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
• An introduction to continuous optimization for imaging
• Dualize, split, randomize: toward fast nonsmooth optimization algorithms
• Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection
• A fast splitting method for efficient split Bregman iterations
• An alternating direction method of multipliers for tensor complementarity problems
• Parameter selection and preconditioning for a graph form solver

This page was built for publication: Fast multiple-splitting algorithms for convex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910883)