Distributed Optimization Algorithm with Superlinear Convergence Rate
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916903383990272 |
|---|---|
| author | Xu, Yeming Guo, Ziyuan Lu, Kaihong Zhang, Huanshui |
| author_facet | Xu, Yeming Guo, Ziyuan Lu, Kaihong Zhang, Huanshui |
| contents | This paper considers distributed optimization problems, where each agent cooperatively minimizes the sum of local objective functions through the communication with its neighbors. The widely adopted distributed gradient method in solving this problem suffers from slow convergence rates, which motivates us to incorporate the second-order information of the objective functions. However, the challenge arises from the unique structure of the inverse of the Hessian matrix, which prevents the direct distributed implementation of the second-order method. We overcome this challenge by proposing a novel optimization framework. The key idea is to transform the distributed optimization problem into an optimal control problem. Using Pontryagin's maximum principle and the associated forward-backward difference equations (FBDEs), we derive a new distributed optimization algorithm that incorporates the second-order information without requiring the computation of the inverse of the Hessian matrix. Furthermore, the superlinear convergence of the proposed algorithm is proved under some mild assumptions. Finally, we also propose a variant of the algorithm to balance the number of iterations and communication. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_12392 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distributed Optimization Algorithm with Superlinear Convergence Rate Xu, Yeming Guo, Ziyuan Lu, Kaihong Zhang, Huanshui Optimization and Control This paper considers distributed optimization problems, where each agent cooperatively minimizes the sum of local objective functions through the communication with its neighbors. The widely adopted distributed gradient method in solving this problem suffers from slow convergence rates, which motivates us to incorporate the second-order information of the objective functions. However, the challenge arises from the unique structure of the inverse of the Hessian matrix, which prevents the direct distributed implementation of the second-order method. We overcome this challenge by proposing a novel optimization framework. The key idea is to transform the distributed optimization problem into an optimal control problem. Using Pontryagin's maximum principle and the associated forward-backward difference equations (FBDEs), we derive a new distributed optimization algorithm that incorporates the second-order information without requiring the computation of the inverse of the Hessian matrix. Furthermore, the superlinear convergence of the proposed algorithm is proved under some mild assumptions. Finally, we also propose a variant of the algorithm to balance the number of iterations and communication. |
| title | Distributed Optimization Algorithm with Superlinear Convergence Rate |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.12392 |