Speaker: Stefano Cipolla Affiliation: University of Edinburgh Time: Friday, 18/06/2021, 16:00
Title: Random multi-block ADMM: an ALM based view for the QP case
Because of its wide versatility and applicability in multiple fields, the n-block alternating direction method of multipliers (ADMM) for solving nonseparable convex minimization problems, has recently attracted the attention of many researchers [1, 2, 4]. When the n-block ADMM is used for the minimization of quadratic functions, it consists in a cyclic update of the primal variables xi for i = 1,...,n in the Gauss-Seidel fashion and a dual ascent type update of the dual variable μ. Despite the fact the connections between ADMM and Gauss-Seidel are quite well known, to the best of our knowledge, an analysis from the purely numerical linear algebra point of view is lacking in literature. Aim of this talk is to present a series of very recent results obtained on this topic which shed further light on basic issues as convergence and efficiency [3].
[1] Chen, C., Li, M., Liu, X., Ye, Y. (2019). Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights. Mathematical Programming, 173(1-2), 37-77.
[2] Chen, C., He, B., Ye, Y., Yuan, X. (2016). The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Mathematical Programming, 155(1-2), 57-79.
[3] Cipolla, S., Gondzio, J (2020). ADMM and inexact ALM: the QP case. arXiv 2012.09230.
[4] Sun, R., Luo, Z. Q., Ye, Y. (2020). On the efficiency of random permutation for ADMM and coordinate descent. Mathematics of Operations Research, 45(1), 233-271.
https://www.dm.unipi.it/webnew/it/seminari/random-multi-block-admm-alm-based...
Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4