Subgradient averaging for multi-agent optimization with different constraint sets
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 objec...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2021
|
| _version_ | 1797106880799047680 |
|---|---|
| author | Romao, L Margellos, K Papachristodoulou, A Notarstefano, G |
| author_facet | Romao, L Margellos, K Papachristodoulou, A Notarstefano, G |
| author_sort | Romao, L |
| collection | OXFORD |
| description | 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 η
k+1 , η > 0. We also analyse this scheme under a step size choice of √ η
k+1 , η > 0, and establish a convergence rate of
O(
ln√k
k
) in objective value. To demonstrate the efficacy of the proposed method, we investigate a robust regression problem
and an ℓ2 regression problem with regularisation. |
| first_indexed | 2024-03-07T07:08:45Z |
| format | Journal article |
| id | oxford-uuid:176fd873-b292-4ec4-ad00-2919bdf04bcf |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:08:45Z |
| publishDate | 2021 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:176fd873-b292-4ec4-ad00-2919bdf04bcf2022-06-06T08:06:37ZSubgradient averaging for multi-agent optimization with different constraint setsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:176fd873-b292-4ec4-ad00-2919bdf04bcfEnglishSymplectic ElementsElsevier2021Romao, LMargellos, KPapachristodoulou, ANotarstefano, GWe 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 η k+1 , η > 0. We also analyse this scheme under a step size choice of √ η k+1 , η > 0, and establish a convergence rate of O( ln√k k ) in objective value. To demonstrate the efficacy of the proposed method, we investigate a robust regression problem and an ℓ2 regression problem with regularisation. |
| spellingShingle | Romao, L Margellos, K Papachristodoulou, A Notarstefano, G Subgradient averaging for multi-agent optimization with different constraint sets |
| title | Subgradient averaging for multi-agent optimization with different constraint sets |
| title_full | Subgradient averaging for multi-agent optimization with different constraint sets |
| title_fullStr | Subgradient averaging for multi-agent optimization with different constraint sets |
| title_full_unstemmed | Subgradient averaging for multi-agent optimization with different constraint sets |
| title_short | Subgradient averaging for multi-agent optimization with different constraint sets |
| title_sort | subgradient averaging for multi agent optimization with different constraint sets |
| work_keys_str_mv | AT romaol subgradientaveragingformultiagentoptimizationwithdifferentconstraintsets AT margellosk subgradientaveragingformultiagentoptimizationwithdifferentconstraintsets AT papachristodouloua subgradientaveragingformultiagentoptimizationwithdifferentconstraintsets AT notarstefanog subgradientaveragingformultiagentoptimizationwithdifferentconstraintsets |