Accelerated primal–dual proximal block coordinate updating methods for constrained convex optimization

Yangyang Xu, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


Block coordinate update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primal–dual BCU method for solving linearly constrained convex program with multi-block variables. The method is an accelerated version of a primal–dual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes an O(1 / t) convergence rate under convexity assumption. We show that the rate can be accelerated to O(1 / t2) if the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can be modified to achieve a linear rate of convergence. The numerical experiments show that the accelerated method performs stably with a single set of parameters while the original method needs to tune the parameters for different datasets in order to achieve a comparable level of performance.

Original languageEnglish (US)
Pages (from-to)91-128
Number of pages38
JournalComputational Optimization and Applications
Issue number1
StatePublished - May 1 2018

Bibliographical note

Funding Information:
This work is partly supported by NSF Grant DMS-1719549 and CMMI-1462408.

Publisher Copyright:
© 2017, Springer Science+Business Media, LLC, part of Springer Nature.


  • Accelerated first-order method
  • Alternating direction method of multipliers (ADMM)
  • Block coordinate update
  • Primal–dual method


Dive into the research topics of 'Accelerated primal–dual proximal block coordinate updating methods for constrained convex optimization'. Together they form a unique fingerprint.

Cite this