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

Zhipeng Tu; Shu Liang

Kybernetika (2024)

  • Issue: 4, page 427-445
  • ISSN: 0023-5954

Abstract

top
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 / 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.

How to cite

top

Tu, Zhipeng, and Liang, Shu. "Distributed dual averaging algorithm for multi-agent optimization with coupled constraints." Kybernetika (2024): 427-445. <http://eudml.org/doc/299543>.

@article{Tu2024,
abstract = {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.},
author = {Tu, Zhipeng, Liang, Shu},
journal = {Kybernetika},
keywords = {distributed optimization; coupled constraints; dual averaging; variational inequality; multi-agent networks},
language = {eng},
number = {4},
pages = {427-445},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Distributed dual averaging algorithm for multi-agent optimization with coupled constraints},
url = {http://eudml.org/doc/299543},
year = {2024},
}

TY - JOUR
AU - Tu, Zhipeng
AU - Liang, Shu
TI - Distributed dual averaging algorithm for multi-agent optimization with coupled constraints
JO - Kybernetika
PY - 2024
PB - Institute of Information Theory and Automation AS CR
IS - 4
SP - 427
EP - 445
AB - 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.
LA - eng
KW - distributed optimization; coupled constraints; dual averaging; variational inequality; multi-agent networks
UR - http://eudml.org/doc/299543
ER -

References

top
  1. Auslender, A., Correa, R., , Comput. Optim. Appl. 17 (2000), 117-130. MR1806249DOI
  2. Auslender, A., Teboulle, M., , Math. Program. 120 (2009), 27-48. MR2496425DOI
  3. Bertsekas, D. P., Tsitsiklis, J. N., Parallel and Distributed Computation: Numerical Methods., Prentice hall Englewood Cliffs, NJ 1989. MR0896902
  4. Borwein, J. M., Zhu, Q. J., Techniques of Variational Analysis., Springer Science and Business Media, New York 2004. Zbl1076.49001MR2144010
  5. Chang, T. H., Nedić, A., Scaglione, A., , IEEE Trans. Automat. Control 59 (2014), 1524-1538. MR3225227DOI
  6. Chen, G., Xu, G., Li, W., Hong, Y., , IEEE Trans. Automat. Control (2023), 1-8. MR4664160DOI
  7. Cherukuri, A., Cortés, J., , IEEE Trans. Control Network Syst. 2 (2015), 226-237. MR3401184DOI
  8. Duchi, J. C., Agarwal, A., Wainwright, M. J., , IEEE Trans. Automat. Control 57 (2011), 592-606. MR2932818DOI
  9. Facchinei, F., Pang, J. S., Finite-dimensional Variational Inequalities and Complementarity Problems., Springer Science and Business Media, 2007. MR1955648
  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. MR2099614
  11. Hiriart-Urruty, J. B., Lemaréchal, C., Convex Analysis and Minimization Algorithms I: Fundamentals., Springer Science and Business Media, 2013. MR1261420
  12. Johansson, B., Keviczky, T., Johansson, M., Johansson, K. H., , In: 47th IEEE Conference on Decision and Control, IEEE 2008, pp. 4185-4190. DOI
  13. Koshal, J., Nedić, A., Shanbhag, U. V., , SIAM J. Optim. 21 (2011), 1046-1081. MR2837563DOI
  14. Liang, S., Zeng, X., Hong, Y., , IEEE Trans. Automat. Control 63 (2017), 1753-1759. MR3807659DOI
  15. Liang, S., Wang, L., Yin, G., , IEEE Trans. Automat. Control 65 (2019), 347-353. MR4052883DOI
  16. Liang, S., Wang, L., Yin, G., , IEEE Trans. Cybernetics 51 (2019), 2529-2539. DOI
  17. Liu, Q., Wang, J., , IEEE Trans. Automat. Control 60 (2015), 3310-3315. MR3432700DOI
  18. Lou, Y., Hong, Y., Wang, S., , Automatica 69 (2016), 289-297. Zbl1338.93026MR3500113DOI
  19. Nedić, A., Ozdaglar, A., , SIAM J. Optim. 19 (2009), 1757-1780. MR2486049DOI
  20. Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course., Springer Science and Business Media, 2003. MR2142598
  21. Nesterov, Y., , Math. Program. 109.2-3 (2007), 319-344. MR2295146DOI
  22. Nesterov, Y., , Math. Program. 120 (2009), 221-259. MR2496434DOI
  23. Nesterov, Y., Shikhman, V., , Europ. J. Oper. Res. 270 (2018), 907-916. MR3814538DOI
  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., , Pacific J. Math. 17 (1966), 497-510. MR0193549DOI
  27. Rockafellar, R. T., , Trans. Amer. Math. Soc. 149 (1970), 75-88. MR0282272DOI
  28. Ruszczynski, A., Nonlinear Optimization., Princeton University Press, 2011. MR2199043
  29. Shafarevich, I. R., Remizov, A. O., Linear Algebra and Geometry., Springer Science and Business Media, 2012. MR2963561
  30. Tu, Z., Li, W., , Kybernetika 57 (2021), 60-77. MR4231857DOI
  31. Xiao, L., Boyd, S., , J. Optim. Theory Appl. 129 (2006), 469-488. MR2281152DOI
  32. Xiao, L., Boyd, S., Kim, S. J., , J. Parallel Distributed Comput. 67 (2007), 33-46. DOI
  33. Yao, J. C., , Math. Oper. Res. 19 (1994), 691-705. MR1288894DOI
  34. Yi, P., Hong, Y., Liu, F., , Systems Control Lett. 83 (2015), 45-52. Zbl1327.93033MR3373270DOI
  35. Yi, P., Hong, Y., Liu, F., , Automatica 74 (2016), 259-269. MR3569392DOI
  36. Yi, P., Pavel, L., , 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., , IEEE Trans. Automat. Control 64 (2018), 1858-1873. MR3951032DOI
  38. Zeng, X., Yi, P., Hong, Y., , IEEE Trans. Automat. Control 62 (2016), 5227-5233. MR3708893DOI
  39. Zhang, Y., Zavlanos, M., , In: 2018 Conference on Decision and Control, IEEE 2018, pp. 1763-1768. DOI
  40. Zhu, M., Martínez, S., , IEEE Trans. Automat. Control 57 (2011), 151-164. MR2917654DOI

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.