Distributed dual averaging algorithm for multi-agent optimization with coupled constraints

Tu, Zhipeng ; Liang, Shu

Kybernetika, Tome 60 (2024) no. 4, pp. 427-445

Abstract (VO)

This paper investigates a distributed algorithm for the multi-agent constrained optimization problem, which is to minimize a global objective function formed by a sum of local convex (possibly nonsmooth) functions under both coupled inequality and affine equality constraints. By introducing auxiliary variables, we decouple the constraints and transform the multi-agent optimization problem into a variational inequality problem with a set-valued monotone mapping. We propose a distributed dual averaging algorithm to find the weak solutions of the variational inequality problem with an $O(1/\sqrt{k})$ convergence rate, where $k$ is the number of iterations. Moreover, we show that weak solutions are also strong solutions that match the optimal primal-dual solutions to the considered optimization problem. A numerical example is given for illustration.

Détail

DOI : 10.14736/kyb-2024-4-0427

Classification : 68W15, 90C33
Keywords: distributed optimization; coupled constraints; dual averaging; variational inequality; multi-agent networks

Bibliographie

[1] Auslender, A., Correa, R.: Primal and dual stability results for variational inequalities. Comput. Optim. Appl. 17 (2000), 117-130. | DOI | MR

[2] Auslender, A., Teboulle, M.: Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities. Math. Program. 120 (2009), 27-48. | DOI | MR

[3] Bertsekas, D. P., Tsitsiklis, J. N.: Parallel and Distributed Computation: Numerical Methods. Prentice hall Englewood Cliffs, NJ 1989. | MR

[4] Borwein, J. M., Zhu, Q. J.: Techniques of Variational Analysis. Springer Science and Business Media, New York 2004. | MR | Zbl

[5] Chang, T. H., Nedić, A., Scaglione, A.: Distributed constrained optimization by consensus-based primal-dual perturbation method. IEEE Trans. Automat. Control 59 (2014), 1524-1538. | DOI | MR

[6] Chen, G., Xu, G., Li, W., Hong, Y.: Distributed mirror descent algorithm with Bregman damping for nonsmooth constrained optimization. IEEE Trans. Automat. Control (2023), 1-8. | DOI | MR

[7] Cherukuri, A., Cortés, J.: Distributed generator coordination for initialization and anytime optimization in economic dispatch. IEEE Trans. Control Network Syst. 2 (2015), 226-237. | DOI | MR

[8] Duchi, J. C., Agarwal, A., Wainwright, M. J.: Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Trans. Automat. Control 57 (2011), 592-606. | DOI | MR

[9] Facchinei, F., Pang, J. S.: Finite-dimensional Variational Inequalities and Complementarity Problems. Springer Science and Business Media, 2007. | MR

[10] Gutman, I., Xiao, W.: Generalized inverse of the Laplacian matrix and some applications. Bulletin (Académie serbe des sciences et des arts. Classe des sciences mathématiques et naturelles. Sciences mathématiques) (2004), 15-23. | MR

[11] Hiriart-Urruty, J. B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals. Springer Science and Business Media, 2013. | MR

[12] Johansson, B., Keviczky, T., Johansson, M., Johansson, K. H.: Subgradient methods and consensus algorithms for solving convex optimization problems. In: 47th IEEE Conference on Decision and Control, IEEE 2008, pp. 4185-4190. | DOI

[13] Koshal, J., Nedić, A., Shanbhag, U. V.: Multiuser optimization: Distributed algorithms and error analysis. SIAM J. Optim. 21 (2011), 1046-1081. | DOI | MR

[14] Liang, S., Zeng, X., Hong, Y.: Distributed nonsmooth optimization with coupled inequality constraints via modified Lagrangian function. IEEE Trans. Automat. Control 63 (2017), 1753-1759. | DOI | MR

[15] Liang, S., Wang, L., Yin, G.: Distributed smooth convex optimization with coupled constraints. IEEE Trans. Automat. Control 65 (2019), 347-353. | DOI | MR

[16] Liang, S., Wang, L., Yin, G.: Distributed dual subgradient algorithms with iterate-averaging feedback for convex optimization with coupled constraint. IEEE Trans. Cybernetics 51 (2019), 2529-2539. | DOI

[17] Liu, Q., Wang, J.: A second-order multi-agent network for bound-constrained distributed optimization. IEEE Trans. Automat. Control 60 (2015), 3310-3315. | DOI | MR

[18] Lou, Y., Hong, Y., Wang, S.: Distributed continuous-time approximate projection protocols for shortest distance optimization problems. Automatica 69 (2016), 289-297. | DOI | MR | Zbl

[19] Nedić, A., Ozdaglar, A.: Approximate primal solutions and rate analysis for dual subgradient methods. SIAM J. Optim. 19 (2009), 1757-1780. | DOI | MR

[20] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Springer Science and Business Media, 2003. | MR

[21] Nesterov, Y.: Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109.2-3 (2007), 319-344. | DOI | MR

[22] Nesterov, Y.: Primal-dual subgradient methods for convex problems. Math. Program. 120 (2009), 221-259. | DOI | MR

[23] Nesterov, Y., Shikhman, V.: Dual subgradient method with averaging for optimal resource allocation. Europ. J. Oper. Res. 270 (2018), 907-916. | DOI | MR

[24] Rabbat, M., Nowak, R.: Distributed optimization in sensor networks. In: Proc. 3rd International Symposium on Information Processing in Sensor Networks, 2004, pp. 20-27.

[25] Regina, S. B., Iusem, A.: Set-Valued Mappings and Enlargements of Monotone Operators. Springer, New York 2003.

[26] Rockafellar, R. T.: Characterization of the subdifferentials of convex functions. Pacific J. Math. 17 (1966), 497-510. | DOI | MR

[27] Rockafellar, R. T.: On the maximality of sums of nonlinear monotone operators. Trans. Amer. Math. Soc. 149 (1970), 75-88. | DOI | MR

[28] Ruszczynski, A.: Nonlinear Optimization. Princeton University Press, 2011. | MR

[29] Shafarevich, I. R., Remizov, A. O.: Linear Algebra and Geometry. Springer Science and Business Media, 2012. | MR

[30] Tu, Z., Li, W.: Multi-agent solver for non-negative matrix factorization based on optimization. Kybernetika 57 (2021), 60-77. | DOI | MR

[31] Xiao, L., Boyd, S.: Optimal scaling of a gradient method for distributed resource allocation. J. Optim. Theory Appl. 129 (2006), 469-488. | DOI | MR

[32] Xiao, L., Boyd, S., Kim, S. J.: Distributed average consensus with least-mean-square deviation. J. Parallel Distributed Comput. 67 (2007), 33-46. | DOI

[33] Yao, J. C.: Variational inequalities with generalized monotone operators. Math. Oper. Res. 19 (1994), 691-705. | DOI | MR

[34] Yi, P., Hong, Y., Liu, F.: Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Systems Control Lett. 83 (2015), 45-52. | DOI | MR | Zbl

[35] Yi, P., Hong, Y., Liu, F.: Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems. Automatica 74 (2016), 259-269. | DOI | MR

[36] Yi, P., Pavel, L.: A distributed primal-dual algorithm for computation of generalized Nash equilibria via operator splitting methods. In: 2017 IEEE 56th Annual Conference on Decision and Control, IEEE 2017, pp. 3841-3846. | DOI

[37] Zeng, X., Liang, S., Hong, Y., Chen, J.: Distributed computation of linear matrix equations: An optimization perspective. IEEE Trans. Automat. Control 64 (2018), 1858-1873. | DOI | MR

[38] Zeng, X., Yi, P., Hong, Y.: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans. Automat. Control 62 (2016), 5227-5233. | DOI | MR

[39] Zhang, Y., Zavlanos, M.: A consensus-based distributed augmented Lagrangian method. In: 2018 Conference on Decision and Control, IEEE 2018, pp. 1763-1768. | DOI

[40] Zhu, M., Martínez, S.: On distributed convex optimization under inequality and equality constraints. IEEE Trans. Automat. Control 57 (2011), 151-164. | DOI | MR