Distributed optimization with inexact oracle

Kui Zhu; Yichen Zhang; Yutao Tang

Kybernetika (2022)

  • Volume: 58, Issue: 4, page 578-592
  • ISSN: 0023-5954

Abstract

top
In this paper, we study the distributed optimization problem using approximate first-order information. We suppose the agent can repeatedly call an inexact first-order oracle of each individual objective function and exchange information with its time-varying neighbors. We revisit the distributed subgradient method in this circumstance and show its suboptimality under square summable but not summable step sizes. We also present several conditions on the inexactness of the local oracles to ensure an exact convergence of the iterative sequences towards the global optimal solution. A numerical example is given to verify the efficiency of our algorithm.

How to cite

top

Zhu, Kui, Zhang, Yichen, and Tang, Yutao. "Distributed optimization with inexact oracle." Kybernetika 58.4 (2022): 578-592. <http://eudml.org/doc/299569>.

@article{Zhu2022,
abstract = {In this paper, we study the distributed optimization problem using approximate first-order information. We suppose the agent can repeatedly call an inexact first-order oracle of each individual objective function and exchange information with its time-varying neighbors. We revisit the distributed subgradient method in this circumstance and show its suboptimality under square summable but not summable step sizes. We also present several conditions on the inexactness of the local oracles to ensure an exact convergence of the iterative sequences towards the global optimal solution. A numerical example is given to verify the efficiency of our algorithm.},
author = {Zhu, Kui, Zhang, Yichen, Tang, Yutao},
journal = {Kybernetika},
keywords = {distributed optimization; inexact oracle; first-order method; multi-agent network; time-varying topology},
language = {eng},
number = {4},
pages = {578-592},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Distributed optimization with inexact oracle},
url = {http://eudml.org/doc/299569},
volume = {58},
year = {2022},
}

TY - JOUR
AU - Zhu, Kui
AU - Zhang, Yichen
AU - Tang, Yutao
TI - Distributed optimization with inexact oracle
JO - Kybernetika
PY - 2022
PB - Institute of Information Theory and Automation AS CR
VL - 58
IS - 4
SP - 578
EP - 592
AB - In this paper, we study the distributed optimization problem using approximate first-order information. We suppose the agent can repeatedly call an inexact first-order oracle of each individual objective function and exchange information with its time-varying neighbors. We revisit the distributed subgradient method in this circumstance and show its suboptimality under square summable but not summable step sizes. We also present several conditions on the inexactness of the local oracles to ensure an exact convergence of the iterative sequences towards the global optimal solution. A numerical example is given to verify the efficiency of our algorithm.
LA - eng
KW - distributed optimization; inexact oracle; first-order method; multi-agent network; time-varying topology
UR - http://eudml.org/doc/299569
ER -

References

top
  1. Alber, Y. I., Iusem, A. N., Solodov, M. V., , Math. Program. 81 (1998), 23-35. MR1617701DOI
  2. Auslender, A., Teboulle, M., , Math. Oper. Res. 29 (2004), 1-26. MR2065711DOI
  3. Bastianello, N., Dall'Anese, E., , In: Proc. European Control Conf. 2021, pp. 2432-2437. DOI
  4. Bertsekas, D. P., Convex optimization algorithms., Athena Scientific, Belmont 2015. MR3558548
  5. Cheng, S., Liang, S., , Kybernetika 56 (2020), 559-577. MR4131743DOI
  6. Correa, R., Lemaréchal, C., , Math. Program. 62 (1993), 261-275. MR1247617DOI
  7. Devolder, O., Glineur, F., Nesterov, Y., , Math. Program. 146 (2014), 37-75. MR3232608DOI
  8. Duchi, J. C., Agarwal, A., Wainwright, M. J., , IEEE Trans. Autom. Control 57 (2011), 592-606. MR2932818DOI
  9. Jakovetić, D., Xavier, J., Moura, J. M., , IEEE Trans. Automat. Control 59 (2014), 1131-1146. MR3214204DOI
  10. Kiwiel, K. C., , SIAM J. Optim. 14 (2004), 807-840. MR2085944DOI
  11. Li, P., Hu, J., , Control Theory Technol. 19 (2021), 499-506. MR4356235DOI
  12. Li, P., Hu, J., Qiu, L., Zhao, Y., Ghosh, B. K., , IEEE Trans. Control Netw. Syst. 9 (2022), 356-366. MR4450544DOI
  13. Li, P., Zhao, Y., Hu, J., Zhang, Y., Ghosh, B. K., , Neurocomputing 407 (2020), 155-162. DOI
  14. Liu, S., Qiu, Z., Xie, L., , Automatica 83 (2017), 162-169. MR3680426DOI
  15. Lou, Y., Shi, G., Johansson, K., Hong, Y., , IEEE Trans. Automat. Control 59 (2014), 1722-1736. MR3232068DOI
  16. Nedić, A., Bertsekas, D. P., , Math. Program. 125 (2010), 75-99. MR2718695DOI
  17. Nedić, A., Liu, J., , Ann. Rev. Control Robot. Auton. Syst. 1 (2018), 77-103. DOI
  18. Nedić, A., Olshevsky, A., Shi, W., , SIAM J. Optim. 27 (2017), 2597-2633. MR3738851DOI
  19. Nedic, A., Ozdaglar, A., , IEEE Trans. Automat. Control 54 (2009), 48-61. MR2478070DOI
  20. Nedić, A., Ozdaglar, A., Parrilo, P. A., , IEEE Trans. Automat. Control 55 (2010), 922-938. MR2654432DOI
  21. Polyak, B., Introduction to optimization., Optimization Software Inc., New York 1987. MR1099605
  22. Qu, G., Li, N., , IEEE Trans. Control Netw. Syst. 5 (2018), 1245-1260. MR3861009DOI
  23. Rasch, J., Antonin, C., , Comput. Optim. Appl. 76 (2020), 381-430. MR4098836DOI
  24. Rockafellar, R. T., , SIAM J. Control Optim. 14 (1976), 877-898. Zbl0358.90053MR0410483DOI
  25. Shi, G., Johansson, K. H., Hong, Y., , IEEE Trans. Automat. Control 58 (2013), 610-622. MR3029459DOI
  26. Shi, W., Ling, Q., Wu, G., Yin, W., , SIAM J. Optim. 25 (2015), 944-966. MR3343366DOI
  27. Tang, Y., Deng, Z., Hong, Y., , IEEE Trans. Cybernet. 49 (2019), 1768-1779. DOI
  28. Tang, Y., Wang, X., , IEEE Trans. Automat. Control 66 (2021), 1733-1740. MR4240200DOI
  29. Tang, Y., Zhu, K., , Int. J. Robust Nonlinear Control 32 (2022), 2084-2099. MR4384879DOI
  30. Xi, C., Khan, U. A., , IEEE Trans. Automat. Control 62 (2017), 3986-3992. MR3684332DOI
  31. Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., Johansson, K. H., , Ann. Rev. Control 47 (2019), 278-305. MR3973217DOI
  32. Yi, P., Hong, Y., Liu, F., , Syst. Control Lett. 83 (2015), 45-52. Zbl1327.93033MR3373270DOI
  33. Zeng, X., Yi, P., Hong, Y., , IEEE Trans. Automat. Control 62 (2017), 5227-5233. MR3708893DOI
  34. Zhang, Y., Deng, Z., Hong, Y., , Automatica 79 (2017), 207-213. MR3627983DOI
  35. Zhu, K., Tang, Y., Primal-dual ε -subgradient method for distributed optimization., J. Syst. Sci. Complex. (2022), accepted. 

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.