×

Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs. (English) Zbl 1478.93258

Summary: In this paper, a class of optimization problems is investigated, where the objective function is the sum of \(N\) convex functions viewed as local functions and the constraints are \(N\) nonidentical closed convex sets. Additionally, it is aimed to solve the considered optimization problem in a distributed manner and thus a sequence of time-varying unbalanced directed graphs is introduced first to depict the information connection topologies. Then, the novel push-sum based constrained optimization algorithm (PSCOA) is developed, where the new gradient descent-like method is applied to settle the involved closed convex set constraints. Furthermore, the rigorous convergence analysis is shown under some standard and common assumptions and it is proved that the developed distributed discrete-time algorithm owns a convergence rate of \(\mathcal{O} (\frac{\ln t}{\sqrt{t}})\) in general case. Specially, the convergence rate of \(\mathcal{O} (\frac{1}{t})\) can be further obtained under the assumption that at least one objective function is strongly convex. Finally, simulation results are given to demonstrate the validity of the theoretical results.

MSC:

93B70 Networked control
90C25 Convex programming
68W15 Distributed algorithms

Software:

D-ADMM
Full Text: DOI

References:

[1] Gharesifard, B.; Cortés, J., Distributed continuous-time convex optimization on weight-balanced digraphs, IEEE Transactions on Automatic Control, 59, 3, 781-786 (2014) · Zbl 1360.90257
[2] Gubin, L. G.; Polyak, B. T.; Raik, E. V., The method of projections for finding the common point of convex sets, USSR Computational Mathematics and Mathematical Physics, 7, 6, 1-24 (1967) · Zbl 0199.51002
[3] Kia, S. S.; Cortés, J.; Martínez, S., Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication, Automatica, 55, 254-264 (2015) · Zbl 1377.93018
[4] Lei, J.; Chen, H.-F.; Fang, H.-T., Primal-dual algorithm for distributed constrained optimization, Systems & Control Letters, 96, 110-117 (2016) · Zbl 1347.93019
[5] Li, H.; Lv, Q.; Huang, T., Distributed projection subgradient algorithm over time-varying general unbalanced directed graphs, IEEE Transactions on Automatic Control, 64, 3, 1309-1316 (2019) · Zbl 1482.90230
[6] Liang, S.; Wang, L. Y.; Yin, G., Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity, Automatica, 105, 298-306 (2019) · Zbl 1429.93009
[7] Lin, P.; Ren, W.; Farrell, J. A., Distributed continuous-time optimization: Nonuniform gradient gains, finite-time convergence, and convex constraint set, IEEE Transactions on Automatic Control, 62, 5, 2239-2253 (2017) · Zbl 1366.90201
[8] Lin, P.; Ren, W.; Yang, C.; Gui, W., Distributed continuous-time and discrete-time optimization with non- uniform unbounded convex constraint sets and nonuniform stepsizes, IEEE Transactions on Automatic Control, 64, 11, 4629-4636 (2019) · Zbl 1482.90160
[9] Liu, Q.; Wang, J., A one-layer projection neural network for nonsmooth optimization subject to linear equalities and bound constraints, IEEE Transactions on Neural Networks Learning Systems, 24, 5, 812-824 (2013)
[10] Liu, Q.; Wang, J., A second-order multi-agent network for bound-constrained distributed optimization, IEEE Transactions on Automatic Control, 60, 12, 3310-3315 (2015) · Zbl 1360.90202
[11] Liu, Q.; Yang, S.; Hong, Y., Constrained consensus algorithms with fixed step size for distributed convex optimization over multiagent networks, IEEE Transactions on Automatic Control, 62, 8, 4259-4265 (2017) · Zbl 1373.90106
[12] Liu, Q.; Yang, S.; Wang, J., A collective neurodynamic approach to distributed constrained optimization, IEEE Transactions on Neural Networks Learning Systems, 28, 8, 1747-1758 (2017)
[13] Mai, V. S.; Abed, E. H., Distributed optimization over directed graphs with row stochasticity and constraint regularity, Automatica, 102, 94-104 (2019) · Zbl 1415.93294
[14] Mota, J. F.C.; Xavier, J. M.F.; Aguiar, P. M.Q.; Puschel, M., D-ADMM: A communication-efficient distributed algorithm for separable optimization, IEEE Transactions on Signal Processing, 60, 10, 2718-2723 (2013) · Zbl 1393.94059
[15] Nedić, A.; Olshevsky, A., Distributed optimization over time-varying directed graphs, IEEE Transactions on Automatic Control, 60, 3, 601-615 (2015) · Zbl 1360.90262
[16] Nedić, A.; Olshevsky, A., Stochastic gradient-push for strongly convex functions on time-varying directed graphs, IEEE Transactions on Automatic Control, 61, 12, 3936-3947 (2016) · Zbl 1359.90142
[17] Nedić, A.; Ozdaglar, A., Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, 54, 1, 48-61 (2009) · Zbl 1367.90086
[18] Nedić, A.; Ozdaglar, A.; Parrilo, P. A., Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, 55, 4, 922-938 (2010) · Zbl 1368.90143
[19] Nedić, A.; Ozdaglar, A.; Shi, W., Achieving geometric convergence for distributed optimization over time-varying graphs, SIAM Journal on Optimization, 27, 4, 2597-2633 (2017) · Zbl 1387.90189
[20] Qiu, Z.; Yang, S.; Wang, J., Distributed constrained optimal consensus of multi-agent systems, Automatica, 68, 209-215 (2016) · Zbl 1334.93019
[21] Qu, G.; Li, N., Harnessing smoothness to accelerate distributed optimization, IEEE Transactions on Control of Network Systems, 5, 3, 1245-1260 (2018) · Zbl 1515.93111
[22] Saadatniaki, F.; Xin, R.; Khan, U. A., Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Transactions on Automatic Control, 65, 11, 4769-4780 (2020) · Zbl 1536.93026
[23] Shi, W.; Ling, Q.; Yuan, K.; Wu, G.; Yin, W., On the linear convergence of the ADMM in decentralized consensus optimization, IEEE Transactions on Signal Processing, 62, 7, 1750-1761 (2014) · Zbl 1394.94532
[24] Wang, J., & Elia, N. (2011). A control perspective for centralized and distributed convex optimization. In Proc. 50th IEEE conf. decision control (pp. 3800-3805). Orlando, FL, USA.
[25] Wei, E., & Ozdaglar, A. (2012). Distributed alternating direction method of multipliers. In Proc. 51st IEEE conf. decision control (pp. 5445-5450). Maui, HI, USA.
[26] Wu, X.; Lu, J., Fenchel dual gradient methods for distributed convex optimization over time-varying networks, IEEE Transactions on Automatic Control, 64, 12, 5148-5155 (2019) · Zbl 1482.90154
[27] Xi, C.; Mai, V. S.; Xin, R.; Abed, E. H.; Khan, U. A., Linear convergence in optimization over directed graphs with row-stochastic matrices, IEEE Transactions on Automatic Control, 63, 10, 3558-3565 (2018) · Zbl 1423.90192
[28] Yang, S.; Liu, Q.; Wang, J., A multi-agent system with a proportional-integral protocol for distributed constrained optimization, IEEE Transactions on Automatic Control, 62, 7, 3461-3467 (2017) · Zbl 1370.90259
[29] Yi, P.; Hong, Y., Quantized subgradient algorithm and data-rate analysis for distributed optimization, IEEE Transactions on Control of Network Systems, 1, 4, 380-392 (2014) · Zbl 1370.90071
[30] Zhu, M.; Martínez, S., On distributed convex optimization under inequality and equality constraints, IEEE Transactions on Automatic Control, 57, 1, 151-164 (2012) · Zbl 1369.90129
[31] Zhu, Y.; Yu, W.; Wen, G.; Chen, G.; Ren, W., Continuous-time distributed subgradient algorithm for convex optimization with general constraints, IEEE Transactions on Automatic Control, 64, 4, 1694-1701 (2019) · Zbl 1482.90164
[32] Zhu, Y.; Yu, W.; Wen, G.; Ren, W., Continuous-time coordination algorithm for distributed convex optimization over weight-unbalanced directed networks, IEEE Transactions on Circuits and Systems II: Express Briefs, 66, 7, 1202-1206 (2019)
[33] Zimmermann, J., Tatarenko, T., Willert, V., & Adamy, J. (2020). Projected push-sum gradient descent-ascent for convex optimization with application to economic dispatch problems. In Proc. 59th IEEE conf. decision control (pp. 542-547). Jeju, South Korea.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.