Kybernetika 58 no. 4, 578-592, 2022

Distributed optimization with inexact oracle

Kui Zhu, Yichen Zhang and Yutao TangDOI: 10.14736/kyb-2022-4-0578

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.

Keywords:

distributed optimization, multi-agent network, inexact oracle, first-order method, time-varying topology

Classification:

65K10, 93A16

paper.pdf

References:

  1. Y. I. Alber, A. N. Iusem and M. V. Solodov: On the projected subgradient method for nonsmooth convex optimization in a Hilbert space. Math. Program. 81 (1998), 23-35.   DOI:10.1007/bf01584842
  2. A. Auslender and M. Teboulle: Interior gradient and epsilon-subgradient descent methods for constrained convex minimization. Math. Oper. Res. 29 (2004), 1-26.   DOI:10.1287/moor.1030.0062
  3. N. Bastianello and E. Dall'Anese: Distributed and inexact proximal gradient method for online convex optimization. In: Proc. European Control Conf. 2021, pp. 2432-2437.   DOI:10.23919/ecc54610.2021.9654953
  4. D. P. Bertsekas: Convex optimization algorithms. Athena Scientific, Belmont 2015.   CrossRef
  5. S. Cheng and S. Liang: Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate. Kybernetika 56 (2020), 559-577.   DOI:10.14736/kyb-2020-3-0559
  6. R. Correa and C. Lemaréchal: Convergence of some algorithms for convex minimization. Math. Program. 62 (1993), 261-275.   DOI:10.1007/BF01585170
  7. O. Devolder, F. Glineur and Y. Nesterov: First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146 (2014), 37-75.   DOI:10.1007/s10107-013-0677-5
  8. J. C. Duchi, A. Agarwal and M. J. Wainwright: Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Trans. Autom. Control 57 (2011), 592-606.   DOI:10.1016/j.disamonth.2011.09.001
  9. D. Jakovetić, J. Xavier and J. M. Moura: Fast distributed gradient methods. IEEE Trans. Automat. Control 59 (2014), 1131-1146.   DOI:10.1109/TAC.2014.2298712
  10. K. C. Kiwiel: Convergence of approximate and incremental subgradient methods for convex optimization. SIAM J. Optim. 14 (2004), 807-840.   DOI:10.1137/S1052623400376366
  11. P. Li and J. Hu: A solution strategy for distributed uncertain economic dispatch problems via scenario theory. Control Theory Technol. 19 (2021), 499-506.   DOI:10.1007/s11768-021-00068-6
  12. P. Li, J. Hu, L. Qiu, Y. Zhao and B. K. Ghosh: A distributed economic dispatch strategy for power-water networks. IEEE Trans. Control Netw. Syst. 9 (2022), 356-366.   DOI:10.1109/TCNS.2021.3104103
  13. P. Li, Y. Zhao, J. Hu, Y. Zhang and B. K. Ghosh: Distributed initialization-free algorithms for multi-agent optimization problems with coupled inequality constraints. Neurocomputing 407 (2020), 155-162.   DOI:10.1016/j.neucom.2020.05.006
  14. S. Liu, Z. Qiu and L. Xie: Convergence rate analysis of distributed optimization with projected subgradient algorithm. Automatica 83 (2017), 162-169.   DOI:10.1016/j.automatica.2017.06.011
  15. Y. Lou, G. Shi, K. Johansson and Y. Hong: Approximate projected consensus for convex intersection computation: Convergence analysis and critical error angle IEEE Trans. Automat. Control 59 (2014), 1722-1736.   DOI:10.1109/TAC.2014.2309261
  16. A. Nedić and D. P. Bertsekas: The effect of deterministic noise in subgradient methods. Math. Program. 125 (2010), 75-99.   DOI:10.1007/s10107-008-0262-5
  17. A. Nedić and J. Liu: Distributed optimization for control. Ann. Rev. Control Robot. Auton. Syst. 1 (2018), 77-103.   DOI:10.1146/annurev-control-060117-105131
  18. A. Nedić, A. Olshevsky and W. Shi: Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J. Optim. 27 (2017), 2597-2633.   DOI:10.1137/16M1084316
  19. A. Nedic and A. Ozdaglar: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control 54 (2009), 48-61.   DOI:10.1109/TAC.2008.2009515
  20. A. Nedić, A. Ozdaglar and P. A. Parrilo: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control 55 (2010), 922-938.   DOI:10.1109/TAC.2010.2041686
  21. B. Polyak: Introduction to optimization. Optimization Software Inc., New York 1987.   CrossRef
  22. G. Qu and N. Li: Harnessing smoothness to accelerate distributed optimization. IEEE Trans. Control Netw. Syst. 5 (2018), 1245-1260.   DOI:10.1109/TCNS.2017.2698261
  23. J. Rasch and C. Antonin: Inexact first-order primal-dual algorithms. Comput. Optim. Appl. 76 (2020), 381-430.   DOI:10.1007/s10589-020-00186-y
  24. R. T. Rockafellar: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976), 877-898.   DOI:10.1137/0314056
  25. G. Shi, K. H. Johansson and Y. Hong: Reaching an optimal consensus: dynamical systems that compute intersections of convex sets. IEEE Trans. Automat. Control 58 (2013), 610-622.   DOI:10.1109/TAC.2012.2215261
  26. W. Shi, Q. Ling, G. Wu and W. Yin: {EXTRA}: An exact first-order algorithm for decentralized consensus optimization. SIAM J. Optim. 25 (2015), 944-966.   DOI:10.1137/14096668X
  27. Y. Tang, Z. Deng and Y. Hong: Optimal output consensus of high-order multiagent systems with embedded technique. IEEE Trans. Cybernet. 49 (2019), 1768-1779.   DOI:10.1109/TCYB.2018.2813431
  28. Y. Tang and X. Wang: Optimal output consensus for nonlinear multiagent systems with both static and dynamic uncertainties. IEEE Trans. Automat. Control 66 (2021), 1733-1740.   DOI:10.1109/TAC.2020.2996978
  29. Y. Tang and K. Zhu: Optimal consensus for uncertain multi-agent systems by output feedback. Int. J. Robust Nonlinear Control 32 (2022), 2084-2099.   DOI:10.1002/rnc.5928
  30. C. Xi and U. A. Khan: Distributed subgradient projection algorithm over directed graphs. IEEE Trans. Automat. Control 62 (2017), 3986-3992.   DOI:10.1109/TAC.2016.2615066
  31. T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin and K. H. Johansson: A survey of distributed optimization. Ann. Rev. Control 47 (2019), 278-305.   DOI:10.1016/j.arcontrol.2019.05.006
  32. P. Yi, Y. Hong and F. Liu: Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Syst. Control Lett. 83 (2015), 45-52.   DOI:10.1016/j.sysconle.2015.06.006
  33. X. Zeng, P. Yi and Y. Hong: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans. Automat. Control 62 (2017), 5227-5233.   DOI:10.1109/TAC.2016.2628807
  34. Y. Zhang, Z. Deng and Y. Hong: Distributed optimal coordination for multiple heterogeneous {Euler–Lagrangian} systems. Automatica 79 (2017), 207-213.   DOI:10.1016/j.automatica.2017.01.004
  35. K. Zhu and Y. Tang: Primal-dual $\varepsilon$-subgradient method for distributed optimization. J. Syst. Sci. Complex. (2022), accepted.   CrossRef