A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems

Abstract

We generalize the well-known primal-dual algorithm proposed by Chambolle and Pock for saddle point problems and relax the condition for ensuring its convergence. The relaxed convergence-guaranteeing condition is effective for the generic convex setting of saddle point problems, and we show by the canonical convex programming problem with linear equality constraints that the relaxed condition is optimal. It also allows us to discern larger step sizes for the resulting subproblems, and thus provides a simple and universal way to improve numerical performance of the original primal-dual algorithm. In addition, we present a structure-exploring heuristic to further relax the convergence-guaranteeing condition for some specific saddle point problems, which could yield much larger step sizes and hence significantly better performance. Effectiveness of this heuristic is numerically illustrated by the classic assignment problem.