Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets
We consider a multi-agent setting with agents exchanging information over a network to solve a convex constrained optimisation problem in a distributed manner. We analyse a new algorithm based on local subgradient exchange under undirected time-varying communication. First, we prove asymptotic conve...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers
2020
|
| _version_ | 1826298135566090240 |
|---|---|
| author | Romao, L Margellos, K Notarstefano, G Papachristodoulou, A |
| author_facet | Romao, L Margellos, K Notarstefano, G Papachristodoulou, A |
| author_sort | Romao, L |
| collection | OXFORD |
| description | We consider a multi-agent setting with agents exchanging information over a network to solve a convex constrained optimisation problem in a distributed manner. We analyse a new algorithm based on local subgradient exchange under undirected time-varying communication. First, we prove asymptotic convergence of the iterates to a minimum of the given optimisation problem for time-varying step-sizes of the form c(k)=ηk+1, for some η > 0. We then restrict attention to step-size choices c(k)=ηk+1√,η>0, and establish a convergence of (ln(k)k√) in objective value. Our algorithm extends currently available distributed subgradient/proximal methods by: (i) accounting for different constraint sets at each node, and (ii) enhancing the convergence speed thanks to a subgradient averaging step performed by the agents. A numerical example demonstrates the efficacy of the proposed algorithm. |
| first_indexed | 2024-03-07T04:42:14Z |
| format | Conference item |
| id | oxford-uuid:d20cd528-1d55-45ec-81ad-3b6b5b4102ad |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:42:14Z |
| publishDate | 2020 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | oxford-uuid:d20cd528-1d55-45ec-81ad-3b6b5b4102ad2022-03-27T08:01:05ZConvergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint setsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:d20cd528-1d55-45ec-81ad-3b6b5b4102adEnglishSymplectic Elements at OxfordInstitute of Electrical and Electronics Engineers2020Romao, LMargellos, KNotarstefano, GPapachristodoulou, AWe consider a multi-agent setting with agents exchanging information over a network to solve a convex constrained optimisation problem in a distributed manner. We analyse a new algorithm based on local subgradient exchange under undirected time-varying communication. First, we prove asymptotic convergence of the iterates to a minimum of the given optimisation problem for time-varying step-sizes of the form c(k)=ηk+1, for some η > 0. We then restrict attention to step-size choices c(k)=ηk+1√,η>0, and establish a convergence of (ln(k)k√) in objective value. Our algorithm extends currently available distributed subgradient/proximal methods by: (i) accounting for different constraint sets at each node, and (ii) enhancing the convergence speed thanks to a subgradient averaging step performed by the agents. A numerical example demonstrates the efficacy of the proposed algorithm. |
| spellingShingle | Romao, L Margellos, K Notarstefano, G Papachristodoulou, A Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets |
| title | Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets |
| title_full | Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets |
| title_fullStr | Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets |
| title_full_unstemmed | Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets |
| title_short | Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets |
| title_sort | convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets |
| work_keys_str_mv | AT romaol convergencerateanalysisofasubgradientaveragingalgorithmfordistributedoptimisationwithdifferentconstraintsets AT margellosk convergencerateanalysisofasubgradientaveragingalgorithmfordistributedoptimisationwithdifferentconstraintsets AT notarstefanog convergencerateanalysisofasubgradientaveragingalgorithmfordistributedoptimisationwithdifferentconstraintsets AT papachristodouloua convergencerateanalysisofasubgradientaveragingalgorithmfordistributedoptimisationwithdifferentconstraintsets |