Distributed primal-dual method on unbalanced digraphs with row stochasticity

Abstract

This study investigates distributed convex optimisation that accounts for the inequality constraints over unbalanced directed graphs. In distributed optimisation, agents exchange information on a network to obtain an optimal solution when they only know their own cost function. We propose a distributed primal-dual subgradient method based on a row stochastic weight matrix that is associated with a communication network. In the proposed method, the normalised left eigenvector of the weight matrix is estimated by a consensus algorithm. Then, the subgradient of the Lagrange function is scaled by the estimated values of the left eigenvector to compensate for the imbalance of the information flow in the network. We show that the pair of estimations for the primal and dual problems converge to an optimal primal-dual solution. We also show the relation between the convergence rate of the proposed algorithm and the step-size rule. A numerical example confirms the validity of the proposed method.

Keywords:

• Distributed primal-dual algorithm
• multi-agent network
• unbalanced directed graph

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This research was partly supported by Japan Society for the Promotion of Science JSPS KAKENHI Grant Numbers JP21K04121.