Distributed Optimization Method And Convergence Analysis For Saddle-point Problem Of Multi-agent System Based On Quantization Information

Distributed optimization has been widely used in many fields such as wireless sensor networks and transportation control. Many scholars have done lots of researches in multi-agent systems and achieved great success. This paper focuses on quantization effects, proposes three algorithms aiming at different conditions and proves the effectiveness of these algorithms by theoretical proof and simulation cases based on the existing distributed optimization algorithms.This paper firstly introduces the distributed saddle-point problem in multi-agent system. The goal of the agents is to cooperatively optimize the global objective function which is a sum of local objective functions under the constraint that only quantized information can be transferred. Motivated by the saddle-point theory, this paper proposes the optimization algorithms based on quantized information by combing and extending the subgradient method and the dual averaging idea and thus solves the problem by computing the saddle point of a concave-convex function.First, taking deterministic quantization into account, this paper studies the distributed saddle point problem with fixed topology and proposes an algorithm which can find the near-optimal solution. The proposed algorithm can converge to the near-optimal solution at rate O?1 T?(T is the iteration number) with precise error bound which depends on the quantization resolution and the dimension of the system. Simulation case is demonstrated to show the convergence results.Second, this paper further researches the saddle-point problem with fixed topology. Different from the first study, distributed primal-dual subgradient algorithm based on probabilistic quantization is proposed to obtain the optimum at rate O?1 T? in terms of probability. Simulation case is displayed to verify the convergence of the algorithm.Finally, this paper further studies the problem of distributed saddle-point problem based on probabilistic quantization over a time-varying network which satisfies the connectivity assumption. This paper presents a method to generate the approximate saddle-point as the optimal solution to the primal problem by using a transition matrix to relate the real-time estimate to the previous estimates. Convergence rate is proved to be O?1 T? and the exact effect of probabilistic quantization is highlighted through theoretical analysis.