A Symmetric Gauss-Seidel Decomposition Theorem for Convex Composite Quadratic Functions

In the paper by Xudong Li, Defeng Sun, and Kim Chuan Toh, titled “A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications”, published in Mathematical Programming 175 (2019) 395–418, we established a symmetric Gauss-Seidel decomposition theorem. This theorem plays a critical role in the successful design of alternating direction methods of multipliers (ADMMs) for multi-block convex optimization problems. It is particularly effective when combined with the convergence analysis of the semi-proximal ADMMs for solving linearly constrained convex optimization problems, as developed in Appendix B of the paper by [Maryam Fazel, Ting Kei Pong, Defeng Sun, and Paul Tseng, titled “Hankel matrix rank minimization with applications to system identification and realization”, Hankel-Matrix-semi-Proximal-ADMM published in SIAM Journal on Matrix Analysis and Applications 34 (2013) 946-977.] Moreover, this decompsoition theorem was used by Liang Chen, Xudong Li, Defeng Sun, and Kim Chuan Toh to prove the equivalence of inexact proximal augmented Lagrangian methods and ADMMs for a class of convex composite programming. Their results were published in “On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming”, Mathematical Programming 185 (2021) 111—161 [Correction to the Proof of Lemma 3.3].