Distributed Push-sum Algorithm With Quantization

Considering a time-varying directional network composed of multiple individuals,each individual in the network has a local objective function that only knows itself,so that the sum of all individual local objective functions can achieve optimal.In the reality communication network,the communication between individuals is limited by bandwidth.This paper considers that only the quantized information can be exchanged between individuals,and combined with Push-surn communication mechanism and distributed sub-gradient algorithm,a distributed Push with quantization is proposed.-sum subgradient algorithm,and gives convergence analysis,convergence speed and numerical experiments.In this thesis,for distributed optimization problem with quantizationa,a distributed Push-sum algorithm with deterministic quantization,a distributed Push-sum algorithm with probability quantization and a distributed Push-sum algorithm with encoder decoder are proposed.First of all,for a distributed Push-sum algorithm with deterministic quantization,it is necessary to transfer and exchange only the information after deterministic quan-tization between individuals.According to the update rules of the algorithm itself,the algorithm is convergent,and the convergence analysis is given.It is also illustrated by numerical experiments.Finally,it is concluded thatF(zi(T))converges to F(z*)at speed O(ln?/?)also has an error term related to the deterministic quantization accuracy.The higher the deterministic quantization accuracy,the closer to the optimal.Secondly,for the distributed Push-sum algorithm with probability quantization,it is considered that only the information after probabilistic quantization can be transmitted and exchanged between individuals.The convergence analysis is also analyzed.Finally,the convergence speed is also O(ln?/?),and there is also an error term related to the probabilistic quan-tization precision.The higher the probability quantization precision,the closer to the optimal..For these two kinds of quantification,it is proved by numerical experiments that the higher the quantization accuracy,the faster the convergence.Finally,for the quantized distributed Push-surn algorithm with encoder decoder,each individual can on-ly exchange and transfer the quantization with the encoder decoder setting,and then give the convergence analysis through theory,and finally get each The individual's state can converge to the vicinity of the optimal solution.