Design Of Distributed Optimization Algorithm For Multi-agent Systems Over Time-varying Unbalanced Graphs

In recent years,the distributed optimization problem based on multi-agent systems receives extensive attention and research.The distributed optimization algorithm makes full use of the high robustness and scalability of the multi-agent network,and distributes the computing tasks to each node to improve processing efficiency.In actual applications,communication failure or node downtime cause an imbalance in the transmission of information,thus it cannot always be guaranteed that agents' communication network is an undirected graph or a directed balanced graph.As a result,the distributed optimization algorithms fail in such an environment.Therefore,the study of distributed optimization algorithms over unbalanced graphs has high actual application value.This thesis studies the design of distributed optimization algorithm for multiagent systems over time-varying unbalanced graphs.The main contributions are summarized as follows:The design of a distributed optimization algorithm over time-varying unbalanced graphs is studied,where delayed gradients are employed.In distributed optimization algorithms based on synchronized clock,it is always necessary to wait for the slowest node to complete its calculation before entering the next iteration.When the gradient calculation takes a long time,the overall calculation efficiency is severely reduced.Thus,the protocol is designed based on delayed gradients while considering networks with communication delays,and the push-sum based distributed delayed dual averaging algorithm is proposed.Theoretical analysis reveals this algorithm can make all nodes converge to the same optimal solution when the communication delay and gradient calculation time are both bounded.Furthermore,as an extension of the proposed algorithm,its online version is proposed,which achieves a sub-linear regret bound.Finally,the proposed algorithms are applied to the logistic regression problems to verify their effectiveness.The design of a distributed online optimization algorithm with privacy protection over timevarying unbalanced graphs is studied.Although the nodes do not directly transmit the cost functions when exchanging information,there is still the risk of being eavesdropped by malicious nodes and causing the leakage of sensitive information.Aiming at this situation,the differentially private online distributed dual averaging push algorithm is proposed,where the differential privacy mechanism is additionally employed to preserve the privacy of participating agents.It is proved that the proposed algorithm achieves sub-linear expected regret bound while maintaining differential privacy,and the trade-off between privacy level and algorithm accuracy is revealed.Finally,the effectiveness of the proposed algorithm is verified by numerical simulations.