Acceleration of Primal-Dual Methods by Preconditioning and Simple Subproblem Procedures

Yanli Liu, Yunbei Xu, Wotao Yin

Submitted

Overview

The very popular methods Primal-Dual Hybrid Gradient (PDHG) and Alternating Direction Method of Multipliers (ADMM) are both good and bad. They are good because they simplify a difficult problem to simple subproblems, many of which have closed-form solutions. However, they can be bad on problems with large condition numbers as they will converge very slowly and take a huge number of iterations to reach just moderate accuracy. To improve their performance especially on the bad cases, researchers have used techniques including diagonal preconditioning and inexact subproblems.

This paper realizes additional one-order-of-magnitude speedup over the state-of-the-art using powerful non-diagonal preconditioning and new simple subproblem procedures for the first time. They work really well! The choices of preconditioners are open. Both low per-iteration cost and global convergence are maintained.

On several typical applications of primal-dual first-order methods, we obtained 4-95x speedups over the state-of-the-art.

Citation

Y. Liu, Y. Xu, W. Yin, Acceleration of primal-dual methods by preconditioning and simple subproblem procedures, UCLA CAM Report 18-59, 2018.


« Back