Distributed online convex optimization with time-varying coupled inequality constraints

This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dua...

Full description

Saved in:
Bibliographic Details
Main Authors: Yi, Xinlei, Li, Xiuxian, Xie, Lihua, Johansson, Karl H.
Other Authors: School of Electrical and Electronic Engineering
Format: Article
Language:English
Published: 2023
Subjects:
Online Access:https://hdl.handle.net/10356/164461
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-164461
record_format dspace
spelling sg-ntu-dr.10356-1644612023-01-26T08:41:19Z Distributed online convex optimization with time-varying coupled inequality constraints Yi, Xinlei Li, Xiuxian Xie, Lihua Johansson, Karl H. School of Electrical and Electronic Engineering Engineering::Electrical and electronic engineering Distributed Optimization Dynamic Mirror Descent This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dual dynamic mirror descent algorithm is proposed to solve this problem, where the local cost, regularization, and constraint functions are held privately and revealed only after each time slot. Without assuming Slater's condition, we first derive regret and constraint violation bounds for the algorithm and show how they depend on the stepsize sequences, the accumulated dynamic variation of the comparator sequence, the number of agents, and the network connectivity. As a result, under some natural decreasing stepsize sequences, we prove that the algorithm achieves sublinear dynamic regret and constraint violation if the accumulated dynamic variation of the optimal sequence also grows sublinearly. We also prove that the algorithm achieves sublinear static regret and constraint violation under mild conditions. Assuming Slater's condition, we show that the algorithm achieves smaller bounds on the constraint violation. In addition, smaller bounds on the static regret are achieved when the objective function is strongly convex. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results. Ministry of Education (MOE) This work was supported in part by the Knut and Alice Wallenberg Foundation, in part by the Swedish Foundation for Strategic Research, in part by the Swedish Research Council, and in part by the Ministry of Education of Republic of Singapore under Grant MoE Tier 1 RG72/19. 2023-01-26T08:41:19Z 2023-01-26T08:41:19Z 2020 Journal Article Yi, X., Li, X., Xie, L. & Johansson, K. H. (2020). Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Transactions On Signal Processing, 68, 731-746. https://dx.doi.org/10.1109/TSP.2020.2964200 1053-587X https://hdl.handle.net/10356/164461 10.1109/TSP.2020.2964200 2-s2.0-85079771660 68 731 746 en RG72/19 IEEE Transactions on Signal Processing © 2020 IEEE. All rights reserved.
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Electrical and electronic engineering
Distributed Optimization
Dynamic Mirror Descent
spellingShingle Engineering::Electrical and electronic engineering
Distributed Optimization
Dynamic Mirror Descent
Yi, Xinlei
Li, Xiuxian
Xie, Lihua
Johansson, Karl H.
Distributed online convex optimization with time-varying coupled inequality constraints
description This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dual dynamic mirror descent algorithm is proposed to solve this problem, where the local cost, regularization, and constraint functions are held privately and revealed only after each time slot. Without assuming Slater's condition, we first derive regret and constraint violation bounds for the algorithm and show how they depend on the stepsize sequences, the accumulated dynamic variation of the comparator sequence, the number of agents, and the network connectivity. As a result, under some natural decreasing stepsize sequences, we prove that the algorithm achieves sublinear dynamic regret and constraint violation if the accumulated dynamic variation of the optimal sequence also grows sublinearly. We also prove that the algorithm achieves sublinear static regret and constraint violation under mild conditions. Assuming Slater's condition, we show that the algorithm achieves smaller bounds on the constraint violation. In addition, smaller bounds on the static regret are achieved when the objective function is strongly convex. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results.
author2 School of Electrical and Electronic Engineering
author_facet School of Electrical and Electronic Engineering
Yi, Xinlei
Li, Xiuxian
Xie, Lihua
Johansson, Karl H.
format Article
author Yi, Xinlei
Li, Xiuxian
Xie, Lihua
Johansson, Karl H.
author_sort Yi, Xinlei
title Distributed online convex optimization with time-varying coupled inequality constraints
title_short Distributed online convex optimization with time-varying coupled inequality constraints
title_full Distributed online convex optimization with time-varying coupled inequality constraints
title_fullStr Distributed online convex optimization with time-varying coupled inequality constraints
title_full_unstemmed Distributed online convex optimization with time-varying coupled inequality constraints
title_sort distributed online convex optimization with time-varying coupled inequality constraints
publishDate 2023
url https://hdl.handle.net/10356/164461
_version_ 1756370572163416064