PRIMAL-DUAL FIRST-ORDER METHODS FOR AFFINELY CONSTRAINED MULTI-BLOCK SADDLE POINT PROBLEMS

We consider the convex-concave saddle point problem min\bfx max\bfy \Phi(x, y), where the decision variables x and/or y are subject to certain multi-block structure and affine coupling constraints, and \Phi(x,y) possesses certain separable structure. Although the minimization counterpart of this problem has been widely studied under the topics of ADMM, this minimax problem is rarely investigated. In this paper, a convenient notion of \epsilon-saddle point is proposed, under which the convergence rate of several proposed algorithms are analyzed. When only one of x and y has multiple blocks and affine constraint, several natural extensions of ADMM are proposed to solve the problem. Depending on the number of blocks and the level of smoothness, \scrO(1/T) or \scrO(1/^\surdT) convergence rates are derived for our algorithms. When both x and y have multiple blocks and affine constraints, a new algorithm called Extra-Gradient Method of Multipliers (EGMM) is proposed. Under desirable smoothness conditions, an \scrO(1/T) rate of convergence can be guaranteed regardless of the number of blocks in x and y. An in-depth comparison between EGMM (fully primal-dual method) and ADMM (approximate dual method) is made over the multi-block optimization problems to illustrate the advantage of the EGMM.