Research On Distributed Optimization Algorithms Based On Collective Dynamics

With the rapid development of big data,cloud computing,5G communications and other fields,a large number of optimization problems in scientific research and engineering practice have gradually shown the characteristics of large-scale data and structural complexity.In this context,distributed optimization emerges by decomposing the complex large-scale optimization problems into subproblems and assigning these subproblems to different individuals,where individuals cooperatively solve problems by communicating with their neighbors.Compared with the traditional distributed discrete-time optimization algorithms,distributed optimization algorithms based on collective dynamics,which rely on the continuous-time neural network models,have a high degree of large-scale parallel computing power and real-time solving ability,so they are widely used in scientific research and engineering practice fields,such as sensor networks,smart grids,machine learning,and artificial intelligence.In this paper,by using algebraic graph theory,convex analysis and monotonic operator theory,projection and cone,differential inclusion system,and convex optimization theory,three types of distributed optimization algorithms based on collective dynamics are designed,which are resource allocation algorithms,kwinners-take-all algorithms and acceleration algorithms over directed graphs.The details are as follows.Firstly,two types of nonsmooth resource allocation problems,which can reflect the cooperation phenomenon between agents,are studied over different communication networks.With regards to the nonsmooth resource allocation problems subjected to coupled inequality and convex set constraints,the projection output feedback of an auxiliary variable is adopted to trace the optimal solution for avoiding the presence of subgradient-based projection operators.Then,based on the consensus protocol for the Lagrange multipliers of coupled constraints,a fully distributed resource allocation algorithm is proposed over connected communication networks.It is proved that the output vector of the algorithm is convergent to the optimal resource allocation from any initial state.With regards to the nonsmooth resource allocation problems subjected to convex set constraints,a potential-based Lagrange function is reformulated by the exact penalty function method to avoid the introduction of additional auxiliary variables.Then,a distributed differentiated projected resource allocation algorithm with a simpler structure and lower complexity is proposed over state-dependent communication networks.It is proved that the connectivity of communication networks can be preserved under the proposed algorithm,and the algorithm converges to the optimal resource allocation with an O(1/t)convergence rate.Secondly,two types of k-winners-take-all problems,which can reflect the competition phenomenon between agents,are studied over connected communication networks.With regards to the k-winners-take-all problems without resolution ratio requirements on the input signal,that is,there exists more than two elements of the input signal take the same value,starting from the equivalent linear programming problem,the multi-group strategy and exact penalty function method are adopted to transform its dual problem into an unconstrained distributed optimization problem.Then,a distributed first-order k-winners-take-all algorithm that consists of a state equation and an output equation,is proposed.In the state equation,the binary consensus protocol is adopted to reduce the requirements for computation and sensing of agents.In the output equation,a simpler comparison filter is designed to eliminate the resolution ratio requirement on the input signal.It is proved that the state equation converges to the equilibrium point with an O(1/t)convergence rate from any initial state,and the output vector is the optimal solution to the k-winners-take-all problem.With regards to the kwinners-take-all problems with resolution ratio requirements on the input signal,that is,the difference between the k-th and(k + 1)-th largest elements of the input signal should be larger than a positive threshold,starting from the equivalent quadratic programming problem,a distributed second-order k-winners-take-all algorithm based on the projected primal-dual gradient flow is proposed by introducing inertial terms that use historical information.Then,by means of the cocoercive operator,it is proved that the algorithm converges asymptotically/exponentially to the k-winners-take-all solution exactly from any initial state.Further,the extensions of the second-order k-winners-take-all algorithm are investigated for solving the constrained k-winners-take-all problems in a distributed manner.Finally,different from the previous two types of decision-making problems,distributed optimization problems that depend on the common variable and subject to convex set constraints are studied over weight-balanced digraphs.To ameliorate the convergence rate,a distributed second-order Nesterov accelerated optimization algorithm based on the projected primal-dual gradient flow is proposed.With the help of the cocoercive operator,it is proved that the algorithm converges to the optimal solution of optimization problems from any initial state.In particular,the damping coefficient of the algorithm is a time-varying function,which can be chosen from a broader class of decreasing functions and does not need to be α/t.