On Distributed Gradient-free Algorithms For Multi-agent Networks

The multi-agent network is composed of multi-agents with ability to work through the coupling of local information interaction and forms of a large-scale networked system, therefore its robustness is strong and the failure of any agent of the network does not affect the normal operation of the whole network, and meanwhile it has a cost saving advantage. Hence, multi-agent networks have been gained widely applications in the fields of artificial intelligence, biology, automation, big data and so on. Previous multi-agent network distributed optimization algorithms usually assume the objective function beig convex and generally solve this kind of problem based on sub-gradient method. But for non convex objective function case, the gradient of the non convex objective function does not exist or the gradient calculation is relatively complicated and thus the sub-gradient algorithm will no longer valid. In this paper, we mainly study the distributed optimization problem of multi-agent networks by using free-gradient algorithm when the objective function is not convex or the sub-gradient maybe nonexistent. In addition, with the development of communication technology, the digital communication replaces the analog communication and thus it is widely used in various fields, for example, the consistency of multi individual network, distributed estimation, etc. Due to the limited bandwidth of the network, the digital communication converts the analog information to digital information through the way of information quantization coding. Therefore, the problem of information quantization is not negligible. Usually, information quantization can be divided into the cases of probabilistic quantization and deterministic quantification. Comparing to the deterministic quantization, the probabilistic quantization has zero mean advantage. But due to the introduction of random factors, multi-agent networks can only achieve convergence in the sense of probability. This paper mainly focus on the cases that the objective function is not convex function or the gradient does not exist, and that the information communication involves in quantization. The main content of this paper can be divided into the following parts:Firstly,a distributed random projection gradient free optimization algorithm is proposed in this paper for multi-agent networks with each agant’s state subject to its constraint set. It is assumed that the objective function of the network is the sum of the objective function of the individual, and each individual only knows its own objective function and its own state constraint set. Due to each agent’s objective function maybe nonconvex, the sub-gradient of each agent’s objective functions hard to be calculated can be handled by using the gradient-free method. Then applying the random projection algorithm at each iteration, the problem of the constrained set maybe unknown or the projection of the constrained set hard to be computed can also be solved. It is proved that, under the proposed algorithm, all agents’states converge to the optimization set almost surely and the objective function of the network also achieves optimal.Secondly, for the case of fixed topology, the influence of probability quantization on the convergence of multiple networks is considered. In real life the digital channel usually has a limited bandwidth; it will limit the data transfer and exchange of information. The digital channel has gradually replaced analog communication channel. Therefore, some scholars put forward the concept of quantization, which is to convert the analog channel into digital channel. This paper considers the distributed optimization of multi-agent network, where the objective function is the sum of the individual local convex objective that is known to each agent and each agent can only interact quantized information with its neighbors. And further explores the effect of probability quantization on the performance of network optimization. Under the assumption that the probabilistic quantization communication is used, this paper further investigates the impact of the probabilistic quantization on the performance of the network optimization. It is proved that if the step size is constant, the state of each agent converges to the neighborhood of the optimal solution of the network.Research shows that the objective function is non convex such a multi-agent network optimization problem, by applying random projection gradient free optimization algorithm can make the objective function and the function reaches its minimum value and has the best solution. At the same time, the individual state can be converged to the optimal solution through the control step size.