Geodesic
Distributed optimization with inexact oracle
Kybernetika, Tome 58 (2022) no. 4, pp. 578-592
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2022-4-0578
Classification : 65K10, 93A16
Keywords: distributed optimization; inexact oracle; first-order method; multi-agent network; time-varying topology 
@article{10_14736_kyb_2022_4_0578,
     author = {Zhu, Kui and Zhang, Yichen and Tang, Yutao},
     title = {Distributed optimization with inexact oracle},
     journal = {Kybernetika},
     pages = {578--592},
     year = {2022},
     volume = {58},
     number = {4},
     doi = {10.14736/kyb-2022-4-0578},
     mrnumber = {4521857},
     zbl = {07655848},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-4-0578/}
}
TY  - JOUR
AU  - Zhu, Kui
AU  - Zhang, Yichen
AU  - Tang, Yutao
TI  - Distributed optimization with inexact oracle
JO  - Kybernetika
PY  - 2022
SP  - 578
EP  - 592
VL  - 58
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-4-0578/
DO  - 10.14736/kyb-2022-4-0578
LA  - en
ID  - 10_14736_kyb_2022_4_0578
ER  - 
%0 Journal Article
%A Zhu, Kui
%A Zhang, Yichen
%A Tang, Yutao
%T Distributed optimization with inexact oracle
%J Kybernetika
%D 2022
%P 578-592
%V 58
%N 4
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-4-0578/
%R 10.14736/kyb-2022-4-0578
%G en
%F 10_14736_kyb_2022_4_0578
Zhu, Kui; Zhang, Yichen; Tang, Yutao. Distributed optimization with inexact oracle. Kybernetika, Tome 58 (2022) no. 4, pp. 578-592. doi: 10.14736/kyb-2022-4-0578

[1] Alber, Y. I., Iusem, A. N., Solodov, M. V.: On the projected subgradient method for nonsmooth convex optimization in a Hilbert space. Math. Program. 81 (1998), 23-35. | DOI | MR

[2] Auslender, A., Teboulle, M.: Interior gradient and epsilon-subgradient descent methods for constrained convex minimization. Math. Oper. Res. 29 (2004), 1-26. | DOI | MR

[3] Bastianello, N., Dall'Anese, E.: Distributed and inexact proximal gradient method for online convex optimization. In: Proc. European Control Conf. 2021, pp. 2432-2437. | DOI

[4] Bertsekas, D. P.: Convex optimization algorithms. Athena Scientific, Belmont 2015. | MR

[5] Cheng, S., Liang, S.: Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate. Kybernetika 56 (2020), 559-577. | DOI | MR

[6] Correa, R., Lemaréchal, C.: Convergence of some algorithms for convex minimization. Math. Program. 62 (1993), 261-275. | DOI | MR

[7] Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146 (2014), 37-75. | DOI | MR

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

[9] Jakovetić, D., Xavier, J., Moura, J. M.: Fast distributed gradient methods. IEEE Trans. Automat. Control 59 (2014), 1131-1146. | DOI | MR

[10] Kiwiel, K. C.: Convergence of approximate and incremental subgradient methods for convex optimization. SIAM J. Optim. 14 (2004), 807-840. | DOI | MR

[11] Li, P., Hu, J.: A solution strategy for distributed uncertain economic dispatch problems via scenario theory. Control Theory Technol. 19 (2021), 499-506. | DOI | MR

[12] Li, P., Hu, J., Qiu, L., Zhao, Y., Ghosh, B. K.: A distributed economic dispatch strategy for power-water networks. IEEE Trans. Control Netw. Syst. 9 (2022), 356-366. | DOI | MR

[13] Li, P., Zhao, Y., Hu, J., Zhang, Y., Ghosh, B. K.: Distributed initialization-free algorithms for multi-agent optimization problems with coupled inequality constraints. Neurocomputing 407 (2020), 155-162. | DOI

[14] Liu, S., Qiu, Z., Xie, L.: Convergence rate analysis of distributed optimization with projected subgradient algorithm. Automatica 83 (2017), 162-169. | DOI | MR

[15] Lou, Y., Shi, G., Johansson, K., Hong, Y.: Approximate projected consensus for convex intersection computation: Convergence analysis and critical error angle. IEEE Trans. Automat. Control 59 (2014), 1722-1736. | DOI | MR

[16] Nedić, A., Bertsekas, D. P.: The effect of deterministic noise in subgradient methods. Math. Program. 125 (2010), 75-99. | DOI | MR

[17] Nedić, A., Liu, J.: Distributed optimization for control. Ann. Rev. Control Robot. Auton. Syst. 1 (2018), 77-103. | DOI

[18] Nedić, A., Olshevsky, A., Shi, W.: Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J. Optim. 27 (2017), 2597-2633. | DOI | MR

[19] Nedic, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control 54 (2009), 48-61. | DOI | MR

[20] Nedić, A., Ozdaglar, A., Parrilo, P. A.: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control 55 (2010), 922-938. | DOI | MR

[21] Polyak, B.: Introduction to optimization. Optimization Software Inc., New York 1987. | MR

[22] Qu, G., Li, N.: Harnessing smoothness to accelerate distributed optimization. IEEE Trans. Control Netw. Syst. 5 (2018), 1245-1260. | DOI | MR

[23] Rasch, J., Antonin, C.: Inexact first-order primal-dual algorithms. Comput. Optim. Appl. 76 (2020), 381-430. | DOI | MR

[24] Rockafellar, R. T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976), 877-898. | DOI | MR | Zbl

[25] Shi, G., Johansson, K. H., Hong, Y.: Reaching an optimal consensus: dynamical systems that compute intersections of convex sets. IEEE Trans. Automat. Control 58 (2013), 610-622. | DOI | MR

[26] Shi, W., Ling, Q., Wu, G., Yin, W.: {EXTRA}: An exact first-order algorithm for decentralized consensus optimization. SIAM J. Optim. 25 (2015), 944-966. | DOI | MR

[27] Tang, Y., Deng, Z., Hong, Y.: Optimal output consensus of high-order multiagent systems with embedded technique. IEEE Trans. Cybernet. 49 (2019), 1768-1779. | DOI

[28] Tang, Y., Wang, X.: Optimal output consensus for nonlinear multiagent systems with both static and dynamic uncertainties. IEEE Trans. Automat. Control 66 (2021), 1733-1740. | DOI | MR

[29] Tang, Y., Zhu, K.: Optimal consensus for uncertain multi-agent systems by output feedback. Int. J. Robust Nonlinear Control 32 (2022), 2084-2099. | DOI | MR

[30] Xi, C., Khan, U. A.: Distributed subgradient projection algorithm over directed graphs. IEEE Trans. Automat. Control 62 (2017), 3986-3992. | DOI | MR

[31] Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., Johansson, K. H.: A survey of distributed optimization. Ann. Rev. Control 47 (2019), 278-305. | DOI | MR

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

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

[34] Zhang, Y., Deng, Z., Hong, Y.: Distributed optimal coordination for multiple heterogeneous Euler–Lagrangian systems. Automatica 79 (2017), 207-213. | DOI | MR

[35] Zhu, K., Tang, Y.: Primal-dual $\varepsilon$-subgradient method for distributed optimization. J. Syst. Sci. Complex. (2022), accepted.

Cité par Sources :