A set of linearised partially-parallel splitting methods for separable convex programs

The proximal partially-parallel splitting method (PPSM), originally proposed in Wang, Desai, and He (2017), is a hybrid mechanism that inherits the nice properties of both Gauss-Seidel and Jacobian substitution procedures for solving the multiple-block convex minimisation problem, whose objective function is the sum of m individual (separable) functions without any shared variables, subject to a linear coupling constraint. In this paper, we extend this work and present some linearised versions of the PPSM, which fully utilise the separable structure and result in subproblems that either have closed-form solutions or are relatively easy to solve as compared to their original nonlinear versions. Global convergence of these linearised methods under the projection contraction algorithmic framework is proven, and furthermore, detailed remarks that serve to clarify the interconnections between these linearised variants are highlighted. Finally, the worst-case O(1/t) convergence rate of these methods under ergodic conditions is also established.