Distributed Constrained Optimization Over Unbalanced Time-Varying Digraphs: A Randomized Constraint Solving Algorithm

Abstract

Despite the recent development of distributed constrained optimization algorithms in the literature, it is still a challenging issue to construct distributed algorithms to efficiently solve the constrained optimization problem with convergence rate guarantees, especially for the case with general constraints and unbalanced time-varying digraphs. This paper aims to investigate the distributed discrete-time optimization problem over time-varying unbalanced digraphs with general constraints including the non-identical closed convex set constraints, the multiple equality and inequality constraints. Toward this end, a new kind of distributed discrete-time algorithms synthesizing some graph topology-dependent row stochastic and column stochastic weight matrix sequences is proposed and employed. In virtue of a randomized constraint solving method, it is theoretically shown that the proposed algorithm can efficiently deal with the considered distributed optimization problem with a large number of inequality constraints and the inequality constraints that cannot be known in advance. Furthermore, the almost sure convergence of the proposed distributed constrained optimization algorithm is theoretically demonstrated under some mild assumptions. It is exhibited that the designed distributed algorithm converges at a rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${ \emph {O}} (\ln (T+1) /\sqrt{T +1})$</tex-math></inline-formula> , like the centralized counterpart. Finally, numerical simulations are given to verify the effectiveness of the present algorithm.