Thanks to its versatility, its simplicity, and its fast convergence, alternating direction method of multipliers (ADMM) is among the most widely used approaches for solving a convex problem in distributed form. However, making it running efficiently is an art that requires a fine tuning of system parameters according to the specific application scenario, and which ultimately calls for a thorough understanding of the hidden mechanisms that control the convergence behavior. In this framework, we aim at providing new theoretical insights on the convergence process and specifically on some constituent matrices of ADMM whose eigenstructure provides a close link with the algorithm's convergence speed. One of the key techniques that we develop allows to effectively locate the eigenvalues of a (symmetric) matrix product, thus being able to estimate the contraction properties of ADMM. In the comparison with the results available from the literature, we are able to strengthen the precision of our speed estimate thanks to the fact that we are solving a joint problem (i.e., we are identifying the spectral radius of the product of two matrices) in place of two separate problems (the product of two matrix norms).

New results on the local linear convergence of ADMM: A joint approach

Erseghe T.
2021

Abstract

Thanks to its versatility, its simplicity, and its fast convergence, alternating direction method of multipliers (ADMM) is among the most widely used approaches for solving a convex problem in distributed form. However, making it running efficiently is an art that requires a fine tuning of system parameters according to the specific application scenario, and which ultimately calls for a thorough understanding of the hidden mechanisms that control the convergence behavior. In this framework, we aim at providing new theoretical insights on the convergence process and specifically on some constituent matrices of ADMM whose eigenstructure provides a close link with the algorithm's convergence speed. One of the key techniques that we develop allows to effectively locate the eigenvalues of a (symmetric) matrix product, thus being able to estimate the contraction properties of ADMM. In the comparison with the results available from the literature, we are able to strengthen the precision of our speed estimate thanks to the fact that we are solving a joint problem (i.e., we are identifying the spectral radius of the product of two matrices) in place of two separate problems (the product of two matrix norms).
File in questo prodotto:
File Dimensione Formato  
New_Results_on_the_Local_Linear_Convergence_of_ADMM_A_Joint_Approach.pdf

Accesso riservato

Tipologia: Published (Publisher's Version of Record)
Licenza: Accesso privato - non pubblico
Dimensione 1.19 MB
Formato Adobe PDF
1.19 MB Adobe PDF Visualizza/Apri   Richiedi una copia
1907.03823v1.pdf

accesso aperto

Tipologia: Preprint (AM - Author's Manuscript - submitted)
Licenza: Altro
Dimensione 544.27 kB
Formato Adobe PDF
544.27 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3411870
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
  • OpenAlex ND
social impact