文章基本信息

标题：Distributed constrained convex optimization over digraphs: A Fenchel dual based approach
本地全文：下载
作者：Yanan Zhu ; Wenwu Yu ; Guanghui Wen 等
期刊名称：IFAC PapersOnLine
印刷版ISSN：2405-8963
出版年度：2020
卷号：53
期号：5
页码：479-482
DOI：10.1016/j.ifacol.2021.04.196
语种：English
出版社：Elsevier
摘要：Recently, a lot of distributed optimization algorithms have been established for solving distribution optimization over weight-unbalanced digraphs. Most of these algorithms are designed in discrete-time setting (see, [6], [7], [11] and the references therein). Recently, continuous-time algorithms have attracted considerable attention in solving distributed optimization over weight-unbalanced digraphs. The pioneering work can be dated back to the literature [9], where a continuous-time push-sum protocol is integrated into gradient flow dynamics. Such a mechanism is further applied to saddle-point dynamics in [10] and [12]. A common assumption in [9, 10] and [12] is that the Laplacian matrix of the weight-unbalanced digraph is required to have a zero column sum. However, such a requirement implies that each agent needs to know its out-degree or adjust its outgoing weights as shown in [6, 7]. This is actually unavailable to the agents communicating over a weightunbalanced digraph. In fact, using the Laplacian matrix with a zero row sum in broadcast-based communication networks is realistic. In this case, some results have been reported in [3] and [14]. Actually, for a weight-unbalanced digraph, the continuous-time algorithm in [3] is only able to minimize the weighted sum of local objective functions instead of the sum in the optimization, where the weights are related to the left eigenvalue of Laplacian matrix associated with zero eigenvalue. Such a limitation was avoided in [14] by using an augmented consensus protocol. However, the algorithm in [14] fails to address the case with the intersection of local constraint sets. Here, we consider the distributed convex optimization problem with the intersection of local constraint sets over a strongly connected digraph, where the global objective function is described as a sum of some agents’ local objective functions. To solve the problem in a distributed way, we first resort to its Fenchel dual problem by introducing local conjugate functions. Then, we propose a distributed Fenchel dual gradient algorithm in continuous-time setting via a two-time-scale system. By using the Lyapunov stability theory, we show that under the proposed algorithm, the agents’ decision variables reach consensus and converge asymptotically to the optimal solution when the local objective functions are strongly convex with locally Lipschitz gradients.
关键词：KeywordsDistributed convex optimizationFenchel dual problemtwo-time-scale systemdigraph