A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
Authors:
- Defeng SunDSDefeng Sun
- Kim-Chuan TohKTKim-Chuan Toh
- Liuqin YangLYLiuqin Yang
- 1 January 2015
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 25 (2) , 882-915
Abstract
In this paper, we consider conic programming problems whose constraints consist of linear equalities, linear inequalities, a nonpolyhedral cone, and a polyhedral cone. A convenient way for solving this class of problems is to apply the directly extended alternating direction method of multipliers (ADMM) to its dual problem, which has been observed to perform well in numerical computations but may diverge in theory. Ideally, one should find a convergent variant which is at least as efficient as the directly extended ADMM in practice. We achieve this goal by designing a convergent semiproximal ADMM (called sPADMM3c for convenience) for convex programming problems having three separable blocks in the objective function with the third part being linear. At each iteration, the proposed sPADMM3c takes one special block coordinate descent (BCD) cycle with the order $1 \rightarrow 3 \rightarrow 2 \rightarrow 3$, instead of the usual $1 \rightarrow 2 \rightarrow 3$ Gauss--Seidel BCD cycle used in the nonconvergent directly extended 3-block ADMM, for updating the variable blocks. Our numerical experiments demonstrate that the convergent method is at least 20% faster than the directly extended ADMM with unit step-length for the vast majority of about 550 large-scale doubly nonnegative semidefinite programming problems with linear equality and/or inequality constraints. This confirms that at least for conic convex programming, one can design a convergent and efficient ADMM with a special BCD cycle of updating the variable blocks.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- An alternating direction-based contraction method for linearly constrained separable convex programming problemsOptimization, 2013
- Hankel Matrix Rank Minimization with Applications to System Identification and RealizationSIAM Journal on Matrix Analysis and Applications, 2013
- An ADM-based splitting method for separable convex programmingComputational Optimization and Applications, 2012
- Alternating Direction Method with Gaussian Back Substitution for Separable Convex ProgrammingSIAM Journal on Optimization, 2012
- On the copositive representation of binary and continuous nonconvex quadratic programsMathematical Programming, 2008
- A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPsMathematical Programming, 2003
- Frequency planning and ramifications of coloringDiscussiones Mathematicae Graph Theory, 2002
- Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational InequalitiesJournal of Optimization Theory and Applications, 2000
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operatorsMathematical Programming, 1992
- A dual algorithm for the solution of nonlinear variational problems via finite element approximationComputers & Mathematics with Applications, 1976