Source-linked AI summary
A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints
Defeng Sun, Kim-Chuan Toh, Liuqin Yang
TL;DR
The paper addresses how to obtain medium-accuracy solutions for four-constraint conic programs without sacrificing either ADMM convergence guarantees or practical efficiency. It develops sPADMM3c, a convergent three-block semi-proximal ADMM with a special block-update cycle, and reports at least a 20% speed advantage over directly extended ADMM on most of about 550 large-scale DNN-SDP problems.
Problem
The central gap is that directly extended ADMM can be numerically effective but may diverge, whereas convergent variants for conic programming have often been substantially slower.
Method
The paper develops sPADMM3c for three-block convex programs with a linear or partially linear third function, using the 1 → 3 → 2 → 3 block-coordinate cycle.
Results
At least 20% faster than directly extended ADMM with unit step-length for the vast majority of about 550 large-scale DNN-SDP problems tested.
Takeaways & Limitations
For the studied conic-programming class, the proposed semi-proximal ADMM combines a convergence guarantee with superior numerical efficiency over directly extended ADMM.
Takeaways & Limitations
The numerical scope is large-scale doubly non-negative SDP problems with linear equality and/or inequality constraints, and the paper notes that general DNN-SDP constraints may lack natural two-easy-block decompositions.
Abstract
from arXiv · showhide
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 \rightarrow 3 \rightarrow 2 \rightarrow 3$, instead of the usual $1 \rightarrow 2 \rightarrow 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.
1 Introduction
The paper targets medium-accuracy solutions for conic programs with four constraint types and addresses the tension between efficient but potentially divergent multi-block ADMM and slower convergent variants. It proposes a convergent semi-proximal approach that exploits a partially linear third block and changes the block-update cycle.
- Problem setting: The target problem combines linear equalities, linear inequalities, a non-polyhedral cone, and a polyhedral cone, including doubly non-negative SDP models.The polyhedral cone is kept separate because this benefits numerical computation.
- Problem setting: The formulation can be represented as a multi-block convex program with separable objective terms and one coupling linear equation.A natural four-block representation is reduced to three blocks by grouping variables associated with a partially linear third function.
- Motivation: Directly extended multi-block ADMM can diverge, while convergent modifications for conic programming have often been reported as 2–3 times slower.The cited divergence result applies even to the directly extended 3-block method with unit step-length.
- Results: The method is reported to be at least 20% faster than directly extended ADMM with unit step-length on the vast majority of about 550 large-scale DNN-SDP problems.The paper presents this as achieving both theoretical convergence and practical efficiency.
- Approach: The proposed sPADMM3c uses the special 1 → 3 → 2 → 3 block-coordinate cycle instead of the usual 1 → 2 → 3 Gauss–Seidel cycle.The extra update of the third block is designed around its linear or partially linear structure.
2 Preliminaries
The preliminaries establish a semi-proximal ADMM framework for two-block convex optimization, including its assumptions, iteration structure, and convergence properties. These results supply the convergence ingredients later used for the three-block method.
- Role in the paper: The two-block convergence results are used as essential ingredients in proving convergence of the proposed three-block sPADMM.The paper also notes that its practically important choice of positive semidefinite proximal terms and τ > 1 is not covered by one cited analysis.
- Algorithm: The two-block sPADMM solves a linearly coupled convex problem by alternating semi-proximal minimizations over y and z, followed by a relaxed dual update.The method uses positive semidefinite operators S and T to keep subproblems tractable while ensuring well-defined iterates.
- Assumptions: Assumption 2.1 requires a relative-interior feasible pair satisfying F*ŷ + G*ẑ = c.This regularity condition supports the optimality and convergence analysis.
- Optimality: The primal-dual optimality system consists of two subdifferential inclusions and the coupling equation F*x̄ + G*z̄ − c = 0.A multiplier satisfying this system is optimal for the dual problem.
- Convergence: Under the stated assumptions, accumulation points of the generated sequence solve the primal problem and associated dual problem.The theorem also establishes summability of selected iterate differences and residual terms.
- Convergence: If the relevant operator sums are positive definite, the entire sequence converges to a unique limit with primal and dual optimal components.The same convergence conclusions extend to the case where the z-part disappears.
3 A convergent 3-block semi-proximal ADMM
The section develops sPADMM3c for three-block convex problems with a linear third function, using a special update cycle and an equivalence to a two-block semi-proximal ADMM to establish convergence.
- 3 A convergent 3-block semi-proximal ADMM: sPADMM3c targets three-block convex optimization problems whose third objective component is linear.The method is formulated for problems with objective f(y)+g(z)+h(w) and one coupling linear constraint.
- 3 A convergent 3-block semi-proximal ADMM: The linear third block can be eliminated explicitly, reducing the problem to an equivalent two-block formulation involving y and z.Under surjectivity of H, w(y,z) is obtained from the equality constraint using (HH*)^-1H.
- 3 A convergent 3-block semi-proximal ADMM: The generated sequence converges to a unique limit whose primal variables solve the three-block problem and whose multiplier solves its dual.The result is stated under the section’s constraint qualification and algorithmic assumptions.
- 3 A convergent 3-block semi-proximal ADMM: The method updates blocks in the order 1 → 3 → 2 → 3 rather than the usual 1 → 2 → 3 Gauss-Seidel cycle.The extra intermediate update computes the third block before updating the second block.
- 3 A convergent 3-block semi-proximal ADMM: The extra third-block update permits convergence for τ=1 and larger step-lengths such as τ=1.618.The paper identifies this larger admissible step-length as a route to faster convergence than the directly extended three-block ADMM.
- 3 A convergent 3-block semi-proximal ADMM: Convergence is proved by showing that sPADMM3c is equivalent to a specifically constructed two-block sPADMM with special semi-proximal terms.This equivalence transfers known two-block convergence results while retaining the simpler three-block implementation.
4 Applications to conic programming
The section applies the convergent three-block ADMM framework to conic programs with equality, inequality, non-polyhedral-cone, and polyhedral-cone constraints, establishing convergence under stated assumptions and designing computationally tractable variants.
- 4 Applications to conic programming: Conic-ADMM3c applies the convergent three-block ADMM to conic programs without inequality constraints.The resulting algorithm is presented for the reduced conic problem and inherits convergence results from the general theory.
- 4 Applications to conic programming: Assumption 4.1 supplies feasible points for the primal and dual formulations, ensuring strong duality and nonempty KKT solutions.The assumption is used as the conic-programming constraint qualification.
- 4 Applications to conic programming: Under Assumption 4.1 and surjectivity of AE, the Conic-ADMM3c sequence is well defined and has accumulation points satisfying the KKT conditions.The theorem states these properties for the algorithm applied to the reduced conic formulation.
- 4 Applications to conic programming: When inequality constraints are few, slack variables convert the problem into a three-block form solvable by Conic-ADMM3c.The paper recommends this formulation specifically when mI is relatively small.
- 4 Applications to conic programming: When inequality constraints are numerous, the paper reformulates the dual using a nonsingular operator D and a linear map B.The reformulation supports a computational treatment of the large-inequality case.
- 4 Applications to conic programming: For the inequality-constrained case, a specific positive semidefinite proximal operator is chosen to simplify computation of the yI update.The resulting Conic-sPADMM3c is analyzed using the same type of convergence argument, with details omitted.
5 Numerical experiments for SDP
The experiments evaluate ADMM3c and related solvers on several classes of doubly non-negative SDP problems, including instances with many inequality constraints. Across the tested problems, ADMM3c is generally fastest while also requiring few iterations in most cases.
- Test problems: The experiments cover DNN-SDP relaxations of BIQ, maximum stable set, QAP, and clustering problems, with and without linear inequality constraints.The test groups include DNN-SDP without inequality constraints and BIQ-derived SDP problems with many inequalities.
- Compared solvers: ADMM3c, SDPAD, 2EBD, and ADMM3g are compared on large-scale DNN-SDP instances, while additional tests compare sPadmm3c, Ladmm4g, sPadmm4d, and sPadmm4d(1).The latter comparison targets extended BIQ problems with many inequality constraints.
- Accuracy results: ADMM3c solved the most instances to accuracy 10^-6 in η or η̂ among the four solvers, followed by SDPAD, ADMM3g, and 2EBD.The iteration limit was 25000, and all four first-order solvers achieved the stated accuracy on large-scale SDP problems.
- Computing time: ADMM3c is generally fastest in computing time, especially for large problems, and its time performance profile significantly outperforms the other three solvers.The comparison includes all tested problems, including those not listed in the detailed table.
- Iteration counts: ADMM3c takes the fewest iterations for most tested problems, although 2EBD often takes fewer iterations on BIQ problems.2EBD’s per-iteration intermediate calculations can offset its iteration-count advantage in computing time.
- Many inequality constraints: For extended BIQ problems, sPadmm3c is clearly faster than sPadmm4d(1) and marginally faster than sPadmm4d with τ = 1.618.For some problems, handling the additional matrix variable can make sPadmm3c slightly slower in time despite requiring fewer iterations.
6 Conclusions
The paper concludes that its convergent 3-block semi-proximal ADMM efficiently solves conic programs with four constraint types, achieving strong performance on large DNN-SDP tests.
- Figure 4 compares iteration performance profiles for sPadmm3c, Ladmm4g, sPadmm4d and sPadmm4d(1).
- The proposed 3-block semi-proximal ADMM is convergent and efficient for medium-accuracy solutions of conic programs with four constraint types.
- At least 20% faster than directly extended semi-proximal ADMM with unit step-length for the vast majority of tested problems.The experiments covered a large number of doubly non-negative SDP problems with equality and/or inequality constraints.