The alternating direction method (ADM) is classical for solving a linearly constrained separable convex programming problem (primal problem), and it is well known that ADM is essentially the application of a concrete form of the proximal point algorithm (PPA) (more precisely, the Douglas-Rachford splitting method) to the corresponding dual problem. This paper shows that an efficient method competitive to ADM can be easily derived by applying PPA directly to the primal problem. More specifically, if the proximal parameters are chosen judiciously according to the separable structure of the primal problem, the resulting customized PPA takes a similar decomposition algorithmic framework as that of ADM. The customized PPA and ADM are equally effective to exploit the separable structure of the primal problem, equally efficient in numerical senses and equally easy to implement. Moreover, the customized PPA is ready to be accelerated by an over-relaxation step, yielding a relaxed customized PPA for the primal problem. We verify numerically the competitive efficiency of the customized PPA to ADM, and the effectiveness of the over-relaxation step. Furthermore, we provide a simple proof for the O(1/t) convergence rate of the relaxed customized PPA.
Article
View A relaxed customized proximal point algorithm for separable convex programming