Research On Distributed Constrained Convex Optimization Over Unbalanced Topologies

With the springing up of the large-scale networks,distributed computation has gained increasing attention since it can split a complex computational task into several subtasks to release the load on computation.This makes the process of completing complex computational tasks much more efficient.As an important part of the distributed computation,distributed optimization has also been extensively researched in recent years due to its wide applications in machine learning problems,source localization problems,estimation problems in sensor networks,congestion control problems and so on.Generally,the optimization problems encountered in reality necessarily involve complicated constraints which make it hard to solve the corresponding optimization problems.Thus,it is of the great practical significance to study the constrained optimization problems.Moreover,the design of the distributed optimization algorithms depends heavily on the communication exchange.However,the communication exchange in reality is always restricted by the asymmetry of the communication topologies and the communication cost.Therefore,it is of great value to lessen the recline of the designed distributed optimization algorithms on the symmetry and the connectivity of the communication topologies in order to achieve greater security of the information transmission and save the communication cost when solving the optimization problems in networks with large scale.Additionally,the convergence rate is the important measure of the performance of the designed algorithm and it can directly decide the needed time and cost produced during the solving of the optimization problem.Accordingly,it is meaningful to further accelerate the convergence rates of the designed algorithms.Taking the research on distributed constrained convex optimization over unbalanced topologies as the topic,this paper mainly focuses on the aspects that successfully settling complicated constraints and lessening the recline on the symmetry of the communication topologies.Additionally,this paper considers accelerating the convergence rates of the proposed distributed algorithms and lessening the recline on the connectivity of the communication topologies.As a result,this paper has accomplished the following works:1)Distributed continuous-time algorithm based on finite-time consensus over timevarying undirected graphs.As for the aspects that successfully settling complicated constraints and employing the finite-time consensus(continuous-time algorithm),consider the convex optimization problem subject to a equality constraint,a inequality constraint and a closed convex set constraint.Moreover,the certain distributed continuous-time algorithm with finite-time consensus protocol is designed over a sequence of time-varying undirected and connected graphs.Additionally,via classical Lyapunov stability theory and convex optimization theory,it is rigorously proved that the generated output variables for all agents under the designed algorithm can reach consensus in finite-time and converge to a common optimal solution of the optimization problem asymptotically.Furthermore,the total dimension of all generated vectors is greatly reduced since the multipliers related to the consensus constraint and equality constraint are unnecessary here.More importantly,this work has laid down a solid foundation for solving the considered problem with a distributed continuous-time algorithm within a finite time.2)Distributed discrete-time algorithms with linear convergence rates over balanced/unbalanced graphs.As for the aspect that successfully settling complicated constraints and achieving the linear convergence rate(discrete-time algorithm),consider designing the distributed discrete-time optimization algorithms with the linear convergence rates for both the unconstrained convex optimization problem and a kind of constrained optimization problem.First,for the unconstrained convex optimization problem,the distributed discrete-time optimization algorithm with linear convergence rate is designed over the balanced graph based on the conjugate gradient method.Furthermore,the method of obtaining the optimal solution by the designed algorithm with finite-time computations is shown.Second,for the convex optimization with the closed convex set constraint,the distributed discrete-time optimization algorithms are designed respectively on the balanced and unbalanced graphs based on the gradient-tracking method.Furthermore,it is proved that the algorithms have linear convergence rates.3)Distributed discrete-time algorithms for constrained optimization problem over static unbalanced graphs.As for the aspects that successfully settling complicated constraints and lessening the recline on the symmetry of the communication topologies(discrete-time algorithm),consider the convex optimization problem with general constraints including multiple equality,multiple inequality and multiple closed convex set constraints,and design the certain distributed discrete-time optimization algorithms over the unbalanced graph.In detail,in the case that no global information is involved,the fully distributed algorithm is proposed by resorting to the gradient descent-like method to deal with both the equality and inequality constraints.Furthermore,the convergence property and the convergence rate are well analyzed and it is proved that the best possible convergence rate of the designed algorithm is O(ln()t+1)/(t+1)0.25).Additionally,in the case that some necessary global information can be obtained in prior,the distributed algorithm is developed with employing the exact penalty function method and the gradient descent-like method to respectively deal with the inequality constraints and the equality constraints.Furthermore,it is proved that the best convergence rate owned by the designed algorithm is O(ln)(t+1)/(t+1)0.5).Thus,the convergence rate is accelerated with some global information employed.4)Distributed discrete-time algorithms for constrained optimization problem over time-varying unbalanced graphs.As for the aspects that successfully settling complicated constraints and lessening the recline on the symmetry as well as the connectivity of the communication topologies(discrete-time algorithm),consider designing the distributed discrete-time optimization algorithms over the time-varying unbalanced graphs sequence to address the constrained convex optimization problems with multiple inequality constraints and multiple closed convex set constraints.In detail,the distributed algorithm employing both row stochastic matrices sequence and column stochastic matrices sequence is designed under the improved push-pull framework,where the gradient descent-like method is adopted to deal with the involved inequality constraints and the projection method is applied in solving the closed convex set constraints.Furthermore,under the assumption that the time-varying unbalanced graphs sequence is uniformly jointly strongly connected,all generated state variables finally converge to a common optimal solution of the considered optimization problem and it is proved that the best convergence rate of the designed algorithm is O(ln(t+1)/(t+1)0.5).