Source-linked AI summary
A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions
Xudong Li, Defeng Sun, Kim-Chuan Toh
TL;DR
The paper addresses how to obtain an efficient convergent multi-block ADMM for convex quadratic conic programming, where direct multi-block extensions may lack convergence guarantees. It proposes a Schur complement based semi-proximal ADMM for models with two proper closed convex functions and arbitrarily many convex quadratic or linear terms. Numerical experiments on QSDP and extensions report superior performance, while the method assumes the relevant additional block functions are convex quadratic.
Problem
The gap is an efficient convergent alternative to direct multi-block semi-proximal ADMM, whose convergence is not guaranteed despite its practical efficiency.
Method
The paper proposes SCB-SPADMM, a Schur complement based semi-proximal ADMM for two proper closed convex functions plus arbitrarily many convex quadratic or linear functions.
Results
Numerical experiments on QSDP and its extensions report convincing results demonstrating the proposed SCB-SPADMM's superior performance.
Takeaways & Limitations
SCB-SPADMM is presented as a flexible method for various multi-block convex optimization problems and for generating good initial points to warm-start rapidly locally convergent methods.
Takeaways & Limitations
The framework assumes each additional objective function θ_i and ϕ_j is convex quadratic.
Abstract
from arXiv · showhide
This paper is devoted to the design of an efficient and convergent {semi-proximal} alternating direction method of multipliers (ADMM) for finding a solution of low to medium accuracy to convex quadratic conic programming and related problems. For this class of problems, the convergent two block semi-proximal ADMM can be employed to solve their primal form in a straightforward way. However, it is known that it is more efficient to apply the directly extended multi-block semi-proximal ADMM, though its convergence is not guaranteed, to the dual form of these problems. Naturally, one may ask the following question: can one construct a convergent multi-block semi-proximal ADMM that is more efficient than the directly extended semi-proximal ADMM? Indeed, for linear conic programming with 4-block constraints this has been shown to be achievable in a recent paper by Sun, Toh and Yang [arXiv preprint arXiv:1404.5378, (2014)]. Inspired by the aforementioned work and with the convex quadratic conic programming in mind, we propose a Schur complement based convergent semi-proximal ADMM for solving convex programming problems, with a coupling linear equality constraint, whose objective function is the sum of two proper closed convex functions plus an arbitrary number of convex quadratic or linear functions. Our convergent semi-proximal ADMM is particularly suitable for solving convex quadratic semidefinite programming (QSDP) with constraints consisting of linear equalities, a positive semidefinite cone and a simple convex polyhedral set. The efficiency of our proposed algorithm is demonstrated by numerical experiments on various examples including QSDP.
1 Introduction
The paper seeks an efficient, simple, and convergent first-order method for convex quadratic conic programming. It targets the efficiency gap between convergent two-block methods and efficient but potentially nonconvergent direct multi-block ADMM extensions.
- Problem formulation: The important QSDP instance includes a positive semidefinite cone, linear equality constraints, and a simple closed convex set.The set may, for example, impose matrix bounds L ≤ W ≤ U.
- Problem formulation: Convex quadratic conic programming is modeled as block-separable convex optimization with closed proper convex functions and linear coupling maps.The formulation treats each block function uniformly, while retaining quadratic structure for algorithm design.
- Motivation: Direct multi-block ADMM avoids the difficult joint minimization in the augmented Lagrangian, but its convergence is not guaranteed.The direct extension is not necessarily convergent for three blocks, despite often working well in practice when τ ≥ 1.
- Motivation: The paper builds on convergent semi-proximal ADMM developments that add an inexpensive step while improving numerical efficiency over direct ADMM extensions.Earlier work established this possibility for three separable blocks with a linear third part.
- Proposed direction: The proposed SCB-SPADMM is designed for a general model with two proper closed convex functions plus an arbitrary number of convex quadratic or linear functions.The paper presents the main algorithm and its convergence results for this model, then studies QSDP and extensions.
2 A Schur complement based semi-proximal augmented Lagrangian method
The section develops a Schur complement based semi-proximal augmented Lagrangian method for a two-block convex problem with a quadratic second function, then establishes convergence under stated regularity and definiteness conditions.
- 2 A Schur complement based semi-proximal augmented Lagrangian method: The generic two-block semi-proximal ADMM uses positive-semidefinite proximal operators to support solvable subproblems and bounded generated sequences.The proximal operators should remain as small as possible while preserving computationally easy updates.
- 2 A Schur complement based semi-proximal augmented Lagrangian method: When the second function is quadratic, the method exploits its structure through a Schur complement based proximal term.The construction uses a majorizing positive-definite operator whose inverse can be computed at moderate cost.
- 2 A Schur complement based semi-proximal augmented Lagrangian method: Under Assumption 2.2 and a nonempty solution set, accumulation points generated by SCB-SPALM solve the primal and dual problems.The theorem allows τ ∈(0, 2), or τ ≥2 subject to an additional summability condition.
- 2 A Schur complement based semi-proximal augmented Lagrangian method: If σ^-1Σf + Tf + FF∗ is positive definite, the generated sequence is well defined and converges to a unique limit solving both problems.The convergence statement is obtained by combining the generic two-block convergence theorem with the Schur complement proposition.
- 2 A Schur complement based semi-proximal augmented Lagrangian method: Compared with a Jacobi-type splitting, the Gauss-Seidel-type decomposition provides the key design idea for extending Schur complement proximal terms to multi-block problems.The quadratic assumption also explains the difference in the proximal-term upper bounds.
3 A Schur complement based semi-proximal ADMM
This section develops SCB-SPADMM, a Schur complement based semi-proximal ADMM for a multi-block convex model with convex quadratic components. The method computes equivalent block updates through sequential elimination and is accompanied by convergence results under stated operator and parameter conditions.
- Model: The model contains two main convex functions plus separable convex quadratic functions θ_i and ϕ_j coupled through one affine constraint Γ(u,y,v,z)=0.The augmented Lagrangian uses θ(y)=∑θ_i(y_i), ϕ(z)=∑ϕ_j(z_j), and the affine residual defined by Γ.
- Implementation: Positive definite majorizing operators E_θi and E_ϕj are selected so their inverses can be computed at moderate cost, while the associated proximal operators remain as small as possible.The construction also defines partial block operators and auxiliary linear terms to implement the equivalent updates.
- Algorithm: SCB-SPADMM is introduced to solve the multi-block model by generating block variables and the multiplier through a four-step iteration.The algorithm updates y-blocks backward, y-blocks forward, z-blocks backward, z-blocks forward, and then updates x.
- Schur complement construction: The method exploits equivalent procedures that eliminate quadratic blocks successively, reducing the joint computation to problems involving progressively fewer blocks.The elimination proceeds from the last block toward the first until only (u,y_1) remains, while preserving equivalence of the computed solution.
- Convergence: Under the theorem’s assumptions and admissible relaxation conditions, accumulation points solve the primal model and the associated dual problem.When additional positive-definiteness conditions hold, the generated sequence converges to a unique limit whose primal and multiplier components solve the corresponding problems.
4 Numerical experiments
The experiments evaluate SCB-SPADMM against ADMM variants on QSDP and nearest correlation matrix problems, using residual-based stopping criteria and performance profiles. Across tested instances, SCB-SPADMM is generally fastest and solves the large-scale QSDP instances reliably.
- Experimental setup: The experiments compare SCB-SPADMM with directly extended ADMM and Gaussian-back-substitution ADMM using common Matlab implementations.For large-scale QSDP, ADMM uses τ = 1 and ADMMGB uses α = 0.99.
- Experimental setup: The solvers terminate at η_qsdp < 10^-6, with a maximum of 25000 iterations for the QSDP tests.
- Large-scale QSDP: SCB-SPADMM is generally fastest on large-scale QSDP, while SCB-SPADMM and ADMM solve all instances to the required accuracy and ADMMGB fails on some.
- Large-scale QSDP: Performance profiles show SCB-SPADMM usually requires the fewest iterations, while SCB-SPADMM and ADMM substantially outperform ADMMGB in computing time.
- Nearest correlation matrix: The spectral-norm formulation is reformulated so that it fits the SCB-SPADMM model, because the algorithm cannot be applied directly to the original dual problem.
- Nearest correlation matrix: For Frobenius-norm H-weighted nearest correlation problems, SCB-SPADMM is more efficient than ADMM and ADMMGB on most tested instances.These experiments use relative residue stopping at η_qsdp < 10^-6.
- Nearest correlation matrix: For spectral-norm H-weighted nearest correlation problems, SCB-SPADMM is reported as much more efficient than ADMM and ADMMGB.
5 Conclusions
The paper proposes SCB-SPADMM for flexible multi-block convex optimization and reports strong numerical performance on QSDP and related extensions. Its stated purpose is to generate good initial points for methods with fast local convergence.
- Conclusions: SCB-SPADMM handles a coupling linear equality constraint with two proper closed convex functions and arbitrarily many convex quadratic or linear objective terms.
- Conclusions: Numerical experiments on QSDP and extensions provide convincing evidence of SCB-SPADMM's superior performance.
- Conclusions: The primary motivation is to quickly generate a good initial point for methods with fast local convergence properties.