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
Meeting link: https://hausdorff.dm.unipi.it/