| Title:
|
Distributed dual averaging algorithm for multi-agent optimization with coupled constraints (English) |
| Author:
|
Tu, Zhipeng |
| Author:
|
Liang, Shu |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
60 |
| Issue:
|
4 |
| Year:
|
2024 |
| Pages:
|
427-445 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
distributed optimization |
| Keyword:
|
coupled constraints |
| Keyword:
|
dual averaging |
| Keyword:
|
variational inequality |
| Keyword:
|
multi-agent networks |
| MSC:
|
68W15 |
| MSC:
|
90C33 |
| DOI:
|
10.14736/kyb-2024-4-0427 |
| . |
| Date available:
|
2024-10-17T08:38:20Z |
| Last updated:
|
2024-10-17 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/152612 |
| . |
| Reference:
|
[1] Auslender, A., Correa, R.: Primal and dual stability results for variational inequalities..Comput. Optim. Appl. 17 (2000), 117-130. MR 1806249, |
| Reference:
|
[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. MR 2496425, |
| Reference:
|
[3] Bertsekas, D. P., Tsitsiklis, J. N.: Parallel and Distributed Computation: Numerical Methods..Prentice hall Englewood Cliffs, NJ 1989. MR 0896902 |
| Reference:
|
[4] Borwein, J. M., Zhu, Q. J.: Techniques of Variational Analysis..Springer Science and Business Media, New York 2004. Zbl 1076.49001, MR 2144010 |
| Reference:
|
[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. MR 3225227, |
| Reference:
|
[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. MR 4664160, |
| Reference:
|
[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. MR 3401184, |
| Reference:
|
[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. MR 2932818, |
| Reference:
|
[9] Facchinei, F., Pang, J. S.: Finite-dimensional Variational Inequalities and Complementarity Problems..Springer Science and Business Media, 2007. MR 1955648 |
| Reference:
|
[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 2099614 |
| Reference:
|
[11] Hiriart-Urruty, J. B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals..Springer Science and Business Media, 2013. MR 1261420 |
| Reference:
|
[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. |
| Reference:
|
[13] Koshal, J., Nedić, A., Shanbhag, U. V.: Multiuser optimization: Distributed algorithms and error analysis..SIAM J. Optim. 21 (2011), 1046-1081. MR 2837563, |
| Reference:
|
[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. MR 3807659, |
| Reference:
|
[15] Liang, S., Wang, L., Yin, G.: Distributed smooth convex optimization with coupled constraints..IEEE Trans. Automat. Control 65 (2019), 347-353. MR 4052883, |
| Reference:
|
[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. |
| Reference:
|
[17] Liu, Q., Wang, J.: A second-order multi-agent network for bound-constrained distributed optimization..IEEE Trans. Automat. Control 60 (2015), 3310-3315. MR 3432700, |
| Reference:
|
[18] Lou, Y., Hong, Y., Wang, S.: Distributed continuous-time approximate projection protocols for shortest distance optimization problems..Automatica 69 (2016), 289-297. Zbl 1338.93026, MR 3500113, |
| Reference:
|
[19] Nedić, A., Ozdaglar, A.: Approximate primal solutions and rate analysis for dual subgradient methods..SIAM J. Optim. 19 (2009), 1757-1780. MR 2486049, |
| Reference:
|
[20] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course..Springer Science and Business Media, 2003. MR 2142598 |
| Reference:
|
[21] Nesterov, Y.: Dual extrapolation and its applications to solving variational inequalities and related problems..Math. Program. 109.2-3 (2007), 319-344. MR 2295146, |
| Reference:
|
[22] Nesterov, Y.: Primal-dual subgradient methods for convex problems..Math. Program. 120 (2009), 221-259. MR 2496434, |
| Reference:
|
[23] Nesterov, Y., Shikhman, V.: Dual subgradient method with averaging for optimal resource allocation..Europ. J. Oper. Res. 270 (2018), 907-916. MR 3814538, |
| Reference:
|
[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. |
| Reference:
|
[25] Regina, S. B., Iusem, A.: Set-Valued Mappings and Enlargements of Monotone Operators..Springer, New York 2003. |
| Reference:
|
[26] Rockafellar, R. T.: Characterization of the subdifferentials of convex functions..Pacific J. Math. 17 (1966), 497-510. MR 0193549, |
| Reference:
|
[27] Rockafellar, R. T.: On the maximality of sums of nonlinear monotone operators..Trans. Amer. Math. Soc. 149 (1970), 75-88. MR 0282272, |
| Reference:
|
[28] Ruszczynski, A.: Nonlinear Optimization..Princeton University Press, 2011. MR 2199043 |
| Reference:
|
[29] Shafarevich, I. R., Remizov, A. O.: Linear Algebra and Geometry..Springer Science and Business Media, 2012. MR 2963561 |
| Reference:
|
[30] Tu, Z., Li, W.: Multi-agent solver for non-negative matrix factorization based on optimization..Kybernetika 57 (2021), 60-77. MR 4231857, |
| Reference:
|
[31] Xiao, L., Boyd, S.: Optimal scaling of a gradient method for distributed resource allocation..J. Optim. Theory Appl. 129 (2006), 469-488. MR 2281152, |
| Reference:
|
[32] Xiao, L., Boyd, S., Kim, S. J.: Distributed average consensus with least-mean-square deviation..J. Parallel Distributed Comput. 67 (2007), 33-46. |
| Reference:
|
[33] Yao, J. C.: Variational inequalities with generalized monotone operators..Math. Oper. Res. 19 (1994), 691-705. MR 1288894, |
| Reference:
|
[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. Zbl 1327.93033, MR 3373270, |
| Reference:
|
[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. MR 3569392, |
| Reference:
|
[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. |
| Reference:
|
[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. MR 3951032, |
| Reference:
|
[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. MR 3708893, |
| Reference:
|
[39] Zhang, Y., Zavlanos, M.: A consensus-based distributed augmented Lagrangian method..In: 2018 Conference on Decision and Control, IEEE 2018, pp. 1763-1768. |
| Reference:
|
[40] Zhu, M., Martínez, S.: On distributed convex optimization under inequality and equality constraints..IEEE Trans. Automat. Control 57 (2011), 151-164. MR 2917654, |
| . |
