.png){kind=icon}
.png){kind=icon}
Return
GradConsensus: Linearly Convergent Algorithm for Reducing Disagreement in Multi-Agent Optimization
.png){kind=icon}
PRE
AI
DOI：10.1109/TNSE.2023.3321757.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this article, we propose a new approach, optimize then agree for minimizing a sum of convex functions, over a directed graph. The optimize then agree approach decouples the optimization step and the consensus step in a multi-agent distributed optimization framework. The key motivation for optimize then agree is to guarantee that the disagreement between the agents' estimates at every iteration of the distributed optimization algorithm remains under any apriori specified tolerance; existing algorithms do not provide such a guarantee which is required in many practical scenarios. In the proposed algorithm, each agent utilizes its locally available function information along with a finite-time approximate consensus protocol to move toward the optimal solution. We establish a global R-linear rate of convergence if the aggregate function is strongly convex and Lipschitz differentiable. We show that under the relaxed assumption of convex and Lipschitz differentiable functions, a Q-linear rate is achieved until reaching a neighborhood of the optimal, that can be managed using the tolerance value specified on the finite-time approximate consensus protocol; no existing method in the literature has such strong convergence guarantees for not necessarily strongly convex functions. The communication overhead for these improved guarantees of our algorithm is within a log k iteration of the algorithm) factor of the traditional algorithms. Further, we numerically demonstrate the efficacy of the proposed algorithm in solving a distributed logistic regression problem.
Keywords:
Optimization
Approximation algorithms
Convergence
Directed graphs
Consensus protocol
Robots
Optimization methods
distributed control
distributed optimization
finite-time consensus
linear convergence
multi-agent networks
Journal
I
IF:
7.9
Papers:
2.5K
Citations:
10.0K