Kybernetika 57 no. 2, 256-271, 2021

A stochastic mirror-descent algorithm for solving AXB=C over an multi-agent system

Yinghui Wang and Songsong ChengDOI: 10.14736/kyb-2021-2-0256

Abstract:

In this paper, we consider a distributed stochastic computation of $AXB=C$ with local set constraints over an multi-agent system, where each agent over the network only knows a few rows or columns of matrixes. Through formulating an equivalent distributed optimization problem for seeking least-squares solutions of $AXB=C$, we propose a distributed stochastic mirror-descent algorithm for solving the equivalent distributed problem. Then, we provide the sublinear convergence of the proposed algorithm. Moreover, a numerical example is also given to illustrate the effectiveness of the proposed algorithm.

Keywords:

multi-agent system, sublinear convergence, stochastic mirror descent algorithm, distributed computation of matrix equation

Classification:

68M15, 93A14

paper.pdf

References:

  1. L. M. Bregman: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics 7 (1967), 200-217.   DOI:10.1016/0041-5553(67)90152-8
  2. G. Chen, X. Zeng and Y. Hong: Distributed optimisation design for solving the Stein equation with constraints. IET Control Theory Appl. 13 (2019), 2492-2499.   DOI:10.1049/iet-cta.2019.0140
  3. 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
  4. W. Deng, X. Zeng and Y. Hong: Distributed computation for solving the Sylvester equation based on optimization. IEEE Control Systems Lett. 4 (2019), 414-419.   DOI:10.1109/LCSYS.2019.2942711
  5. M. R. Gholami, M. Jansson and E. G. Ström et al.: Diffusion estimation over cooperative multi-agent networks with missing data. IEEE Trans. Signal Inform. Process. over Networks 2 (2016), 27-289.   DOI:10.1109/tsipn.2016.2570679
  6. G. Lan, S. Lee and Y. Zhou: Communication-efficient algorithms for decentralized and stochastic optimization. Math. Programm. 180 (2020), 237-284.   DOI:10.1007/s10107-018-1355-4
  7. J. Lei, U. V. Shanbhag and J. S. Pang et al.: On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games. Math. Oper. Res. 45 (2020), 157-190.   DOI:10.1287/moor.2018.0986
  8. J. Liu, A. S. Morse, A. Nedic and et a.: Exponential convergence of a distributed algorithm for solving linear algebraic equations. Automatica 83 (2017), 37-46.   DOI:10.1016/j.automatica.2017.05.004
  9. S. Mou, J. Liu and A. S. Morse: A distributed algorithm for solving a linear algebraic equation. IEEE Trans. Automat. Control 60 (2015), 2863-2878.   DOI:10.1109/TAC.2015.2414771
  10. S. S. Ram, A. Nedic and V. V. Veeravalli: Distributed stochastic subgradient projection algorithms for convex optimization. J. Optim. Theory Appl. 147 (2010), 516-545.   DOI:10.1007/s10957-010-9737-7
  11. G. Shi, B. D. O. Anderson and U. Helmke: Network flows that solve linear equations. IEEE Trans. Automat. Control 62 (2016), 2659-2674.   DOI:10.1109/TAC.2016.2612819
  12. Y. Wang, P. Lin and Y. Hong: Distributed regression estimation with incomplete data in multi-agent networks. Science China Inform. Sci. 61 (2018), 092202.   CrossRef
  13. Y. Wang, P. Lin and H. Qin: Distributed classification learning based on nonlinear vector support machines for switching networks. Kybernetika 53 (2017), 595-611.   DOI:10.14736/kyb-2017-4-0595
  14. Y. Wang, W. Zhao and Y. Hong et al.: Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks. SIAM J. Control Optim. 57 (2019), 2821-2842.   DOI:/10.1137/18M119046X
  15. D. Yuan, Y. Hong and D. W. C. Ho et al.: Optimal distributed stochastic mirror descent for strongly convex optimization. Automatica 90(2018), 196-203.   DOI:10.1016/j.automatica.2017.12.053
  16. D. Yuan, Y. Hong and D. W. C. Ho et al.: Distributed mirror descent for online composite optimization. IEEE Trans. Automat. Control (2020).   CrossRef
  17. X. Zeng, S. Liang and Y. Hong et al.: Distributed computation of linear matrix equations: An optimization perspective. IEEE Trans. Automat. Control 64 (2018), 1858-1873.   DOI:10.1109/TAC.2018.2847603