Optimization Online


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

Yanli Liu (yanli***at***math.ucla.edu)
Yunbei Xu (yunbei.xu***at***gsb.columbia.edu)
Wotao Yin (wotaoyin***at***math.ucla.edu)

Abstract: Primal-Dual Hybrid Gradient (PDHG) and Alternating Direction Method of Multipliers (ADMM) are two widely-used first-order optimization methods. They reduce a difficult problem to simple subproblems, so they are easy to implement and have many applications. As first-order methods, however, they are sensitive to problem conditions and can struggle to reach the desired accuracy. To improve their performance, researchers have proposed techniques such as diagonal preconditioning and inexact subproblems. This paper realizes additional speedup about one order of magnitude. Specifically, we choose non-diagonal preconditioners that are much more effective than diagonal ones. Because of this, we lose closed-form solutions to some subproblems, but we found simple procedures to replace them such as a few proximal-gradient iterations or a few epochs of proximal block-coordinate descent, which are in closed forms. We show global convergence while fixing the number of those steps in every outer iteration. Therefore, our method is reliable and straightforward. Our method opens the choices of preconditioners and maintains both low per-iteration cost and global convergence. Consequently, on several typical applications of primal-dual first-order methods, we obtain 495 speedup over the existing state-of-the-art.

Keywords: Primal-Dual Hybrid Gradient, Alternating Direction Method of Multipliers, preconditioning, fixed number of inner iterations, structured subproblem

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Liu, Yanli, Yunbei Xu, and Wotao Yin. "Acceleration of Primal-Dual Methods by Preconditioning and Simple Subproblem Procedures." arXiv preprint arXiv:1811.08937 (2018).

Download: [PDF]

Entry Submitted: 11/26/2018
Entry Accepted: 11/26/2018
Entry Last Modified: 09/08/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society