On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions

DOI10.1007/S10957-016-0877-2zbMATH Open1342.90130arXiv1502.00098OpenAlexW2274628055MaRDI QIDQ301734FDOQ301734

Authors: Ying Cui, Xudong Li, Kim-Chuan Toh, Defeng Sun 

Publication date: 1 July 2016

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Abstract: In this paper, we establish the convergence properties for a majorized alternating direction method of multipliers (ADMM) for linearly constrained convex optimization problems whose objectives contain coupled functions. Our convergence analysis relies on the generalized Mean-Value Theorem which plays an important role to properly control the cross terms due to the presence of coupled objective functions. Our results in particular show that directly applying 2-block ADMM with a large step length to the linearly constrained convex optimization problem with a quadratically coupled objective function is convergent under mild conditions. We also provide several iteration complexity results for the algorithm.

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

Recommendations

• Convergence of ADMM for optimization problems with nonseparable nonconvex objective and linear constraints
• Convergence of generalized alternating direction method of multipliers for nonseparable nonconvex objective with linear constraints
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
• Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
• On the linear convergence of the alternating direction method of multipliers

zbMATH Keywords

majorizationnonsmooth analysisiteration complexityconvex quadratic programmingcoupled objective function

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Title not available (Why is that?)
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Title not available (Why is that?)
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
• Title not available (Why is that?)
• Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
• Lectures on numerical methods for non-linear variational problems
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
• A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
• A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
• Convergence rate analysis of several splitting schemes
• Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data

Cited In (29)

• On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
• The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates
• Iteration-complexity analysis of a generalized alternating direction method of multipliers
• Convergence of Bregman Peaceman-Rachford splitting method for nonconvex nonseparable optimization
• Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights
• A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
• Alternating direction method of multipliers for linear hyperspectral unmixing
• Decomposition methods for computing directional stationary solutions of a class of nonsmooth nonconvex optimization problems
• Pointwise and ergodic convergence rates of a variable metric proximal alternating direction method of multipliers
• A primal-dual dynamical approach to structured convex minimization problems
• A proximal alternating direction method for multi-block coupled convex optimization
• Randomized primal-dual proximal block coordinate updates
• Convergence Analysis of Generalized ADMM with Majorization for Linearly Constrained Composite Convex Optimization
• Majorized iPADMM for Nonseparable Convex Minimization Models with Quadratic Coupling Terms
• Image reconstruction by minimizing curvatures on image surface
• An inexact majorized proximal alternating direction method of multipliers for diffusion tensors
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
• ADMM for multiaffine constrained optimization
• Convergence analysis of an improved Bregman-type Peaceman-Rachford splitting algorithm for nonconvex nonseparable linearly constrained optimization problems
• Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
• An accelerated proximal alternating direction method of multipliers for optimal decentralized control of uncertain systems
• Improved Pointwise Iteration-Complexity of A Regularized ADMM and of a Regularized Non-Euclidean HPE Framework
• A linear approximate Bregman-type Peaceman-Rachford splitting method for nonconvex nonseparable optimization
• A partially inexact proximal alternating direction method of multipliers and its iteration-complexity analysis
• A partially feasible Jacobi-type distributed SQO method for two-block general linearly constrained smooth optimization
• Two linear proximal Peaceman-Rachford splitting algorithms for nonconvex and nonsmooth nonseparable 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
• On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM

This page was built for publication: On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions

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