A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints

Abstract

The objective of this paper is to design an efficient and convergent alternating direction method of multipliers (ADMM) for finding a solution of medium accuracy to conic programming problems whose constraints consist of linear equalities, linear inequalities, a non-polyhedral cone and a polyhedral cone. For this class of problems, one may apply the directly extended ADMM to their dual, which can be written in the form of convex programming with four separable blocks in the objective function and a coupling linear equation constraint. Indeed, the directly extended ADMM, though may diverge in theory, often performs much better numerically than many of its variants with theoretical convergence guarantee. 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 semi-proximal 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\to 3\to 2\to 3$, instead of the usual $1\to 2\to 3$ Gauss-Seidel BCD cycle used in the non-convergent directly extended $3$-block ADMM, for updating the variable blocks. Our extensive numerical tests on the important class of doubly non-negative semidefinite programming (SDP) problems with linear equality and/or inequality constraints demonstrate that our 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 problems tested.

37 pages, 4 figures, 3 tables. In this revised version, we re-organized the original Section2: the original Section 2.2 now is the new Section 2; the original Section 2.1 and 2.3 now are combined as the new Section 3.1; the original Section 2.4 and 2.5 now are combined as the new Section 3.2

References in corpus (1)

• A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions

Cited by in corpus (6)

• On the Asymptotic Superlinear Convergence of the Augmented Lagrangian Method for Semidefinite Programming with Multiple Solutions
• A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions
• A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization
• A corrected semi-proximal ADMM for multi-block convex optimization and its application to DNN-SDPs
• SDPNAL$+$: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints
• Symmetric Gauss-Seidel Technique Based Alternating Direction Methods of Multipliers for Transform Invariant Low-Rank Textures Problem