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

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 article aims to investigate the distributed discrete-time optimization problem over time-varying unbalanced digraphs with general constraints including the nonidentical closed convex set constraints, the multiple equality, and inequality constraints. Toward this end, a new kind of distributed discrete-time algorithm 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. The explicit convergence rate for the designed distributed algorithm is provided, like the centralized counterpart. Finally, numerical simulations are given to verify the effectiveness of the present algorithm.