We consider a multi-agent setting with agents exchanging information over a possibly time-varying network, aiming at minimising a separable objective function subject to constraints. To achieve this objective we propose a novel subgradient averaging algorithm that allows for non-differentiable objective functions and different constraint sets per agent. Allowing different constraints per agent simultaneously with a time-varying communication network constitutes a distinctive feature of our approach, extending existing results on distributed subgradient methods. To highlight the necessity of dealing with a different constraint set within a distributed optimisation context, we analyse a problem instance where an existing algorithm does not exhibit a convergent behaviour if adapted to account for different constraint sets. For our proposed iterative scheme we show asymptotic convergence of the iterates to a minimum of the underlying optimisation problem for step sizes of the form [Formula Presented], η>0. We also analyse this scheme under a step size choice of [Formula Presented], η>0, and establish a convergence rate of O([Formula Presented]) in objective value. To demonstrate the efficacy of the proposed method, we investigate a robust regression problem and an ℓ2 regression problem with regularisation.
Subgradient averaging for multi-agent optimisation with different constraint sets / Romao L.; Margellos K.; Notarstefano G.; Papachristodoulou A.. - In: AUTOMATICA. - ISSN 0005-1098. - ELETTRONICO. - 131:(2021), pp. 109738.1-109738.14. [10.1016/j.automatica.2021.109738]
Subgradient averaging for multi-agent optimisation with different constraint sets
Romao L.
;Notarstefano G.;
2021
Abstract
We consider a multi-agent setting with agents exchanging information over a possibly time-varying network, aiming at minimising a separable objective function subject to constraints. To achieve this objective we propose a novel subgradient averaging algorithm that allows for non-differentiable objective functions and different constraint sets per agent. Allowing different constraints per agent simultaneously with a time-varying communication network constitutes a distinctive feature of our approach, extending existing results on distributed subgradient methods. To highlight the necessity of dealing with a different constraint set within a distributed optimisation context, we analyse a problem instance where an existing algorithm does not exhibit a convergent behaviour if adapted to account for different constraint sets. For our proposed iterative scheme we show asymptotic convergence of the iterates to a minimum of the underlying optimisation problem for step sizes of the form [Formula Presented], η>0. We also analyse this scheme under a step size choice of [Formula Presented], η>0, and establish a convergence rate of O([Formula Presented]) in objective value. To demonstrate the efficacy of the proposed method, we investigate a robust regression problem and an ℓ2 regression problem with regularisation.File | Dimensione | Formato | |
---|---|---|---|
870863_disclaimer.pdf
Open Access dal 03/06/2023
Tipo:
Postprint
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione
663.41 kB
Formato
Adobe PDF
|
663.41 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.