GMRES-accelerated ADMM for quadratic objectives

DOI10.1137/16M1059941zbMATH Open1402.49025arXiv1601.06200OpenAlexW3105492150MaRDI QIDQ4554067FDOQ4554067

Authors: Richard Zhang, J. K. White 

Publication date: 7 November 2018

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

Abstract: We consider the sequence acceleration problem for the alternating direction method-of-multipliers (ADMM) applied to a class of equality-constrained problems with strongly convex quadratic objectives, which frequently arise as the Newton subproblem of interior-point methods. Within this context, the ADMM update equations are linear, the iterates are confined within a Krylov subspace, and the General Minimum RESidual (GMRES) algorithm is optimal in its ability to accelerate convergence. The basic ADMM method solves a $kappa$-conditioned problem in $O(sqrtkappa)$ iterations. We give theoretical justification and numerical evidence that the GMRES-accelerated variant consistently solves the same problem in $O(kapp{a}^{1/4})$ iterations for an order-of-magnitude reduction in iterations, despite a worst-case bound of $O(sqrtkappa)$ iterations. The method is shown to be competitive against standard preconditioned Krylov subspace methods for saddle-point problems. The method is embedded within SeDuMi, a popular open-source solver for conic optimization written in MATLAB, and used to solve many large-scale semidefinite programs with error that decreases like $O(1/k^2)$, instead of $O(1/k)$, where $k$ is the iteration index.

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

Recommendations

• A general framework for ADMM acceleration
• Efficient semidefinite programming with approximate ADMM
• Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
• Fast alternating direction multipliers method by generalized Krylov subspaces
• Generalized alternating direction method of multipliers: new theoretical insights and applications

zbMATH Keywords

ADMMaugmented LagrangianGMRESKrylov subspacemethod of multipliersalternating directionsequence acceleration

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22) Newton-type methods (49M15) Numerical methods of relaxation type (49M20) Acceleration of convergence in numerical analysis (65B99)

Cites Work

• NESTA: A fast and accurate first-order method for sparse recovery
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• SDPLIB 1.2, a library of semidefinite programming test problems
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems
• Conic optimization via operator splitting and homogeneous self-dual embedding
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new polynomial-time algorithm for linear programming
• Smooth minimization of non-smooth functions
• Introductory lectures on convex optimization. A basic course.
• On the global and linear convergence of the generalized alternating direction method of multipliers
• On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• Title not available (Why is that?)
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• Anderson acceleration for fixed-point iterations
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Title not available (Why is that?)
• Semidefinite Programming
• Fast alternating direction optimization methods
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Title not available (Why is that?)
• A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
• Numerical solution of saddle point problems
• On Solving Block-Structured Indefinite Linear Systems
• Uncertainty principles and ideal atomic decomposition
• Title not available (Why is that?)
• Title not available (Why is that?)
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Minimum residual methods for augmented systems
• Optimization of the Hermitian and skew-Hermitian splitting iteration for saddle-point problems
• Block triangular preconditioners for symmetric saddle-point problems
• On the eigenvalues of a class of saddle point matrices
• Constraint Preconditioning for Indefinite Linear Systems
• A Preconditioner for Generalized Saddle Point Problems
• Spectral Properties of the Hermitian and Skew-Hermitian Splitting Preconditioner for Saddle Point Problems
• Analysis of iterative methods for saddle point problems: A unified approach
• Title not available (Why is that?)
• A Preconditioned Iterative Method for Saddlepoint Problems
• Title not available (Why is that?)
• From Potential Theory to Matrix Iterations in Six Steps
• Complementarity and nondegeneracy in semidefinite programming
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Covariance selection for nonchordal graphs via chordal embedding
• A Preconditioning Technique for Indefinite Systems Resulting from Mixed Approximations of Elliptic Problems
• Convergence Theory of Nonlinear Newton–Krylov Algorithms
• Matrix-free interior point method
• Smoothing technique and its applications in semidefinite optimization
• Solving some large scale semidefinite programs via the conjugate residual method
• Incomplete Cholesky Factorizations with Limited Memory
• Unified analysis of preconditioning methods for saddle point matrices.
• A matrix-free preconditioner for sparse symmetric positive definite systems and least-squares problems
• A Hybrid GMRES Algorithm for Nonsymmetric Linear Systems
• Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
• Bounds for iterates, inverses, spectral variation and fields of values of non-normal matrices
• Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method
• Preconditioning indefinite systems in interior point methods for optimization
• Title not available (Why is that?)
• Sampling from large matrices
• Extremal Polynomials with Application to Richardson Iteration for Indefinite Linear Systems
• On measures of nonnormality of matrices
• A primal-dual potential reduction method for problems involving matrix inequalities
• Logarithmic barriers for sparse matrix cones
• Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
• An accelerated linearized alternating direction method of multipliers
• Title not available (Why is that?)
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• An inexact dual logarithmic barrier method for solving sparse semidefinite programs

Cited In (5)

• Fast and stable nonconvex constrained distributed optimization: the ELLADA algorithm
• On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
• On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM
• Efficient semidefinite programming with approximate ADMM

Uses Software

• Matlab
• SDPLIB
• SeDuMi
• COL
• NESTA
• Eigtool
• Anderson
• SCS

This page was built for publication: GMRES-accelerated ADMM for quadratic objectives

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