Distributed Optimization and Scaling Design for Solving Sylvester Equations

CHENG Songsong, YU Xin, ZENG Xianlin, LIANG Shu, HONG Yiguang

Journal of Systems Science & Complexity ›› 2024, Vol. 37 ›› Issue (6) : 2487-2510.

PDF(834 KB)
中国科学院数学与系统科学研究院期刊网
JSSC
PDF(834 KB)
Journal of Systems Science & Complexity ›› 2024, Vol. 37 ›› Issue (6) : 2487-2510. DOI: 10.1007/s11424-024-3407-6

Distributed Optimization and Scaling Design for Solving Sylvester Equations

  • CHENG Songsong1, YU Xin1, ZENG Xianlin2, LIANG Shu3, HONG Yiguang3
Author information +
History +

Abstract

This paper develops distributed algorithms for solving Sylvester equations. The authors transform solving Sylvester equations into a distributed optimization problem, unifying all eight standard distributed matrix structures. Then the authors propose a distributed algorithm to find the least squares solution and achieve an explicit linear convergence rate. These results are obtained by carefully choosing the step-size of the algorithm, which requires particular information of data and Laplacian matrices. To avoid these centralized quantities, the authors further develop a distributed scaling technique by using local information only. As a result, the proposed distributed algorithm along with the distributed scaling design yields a universal method for solving Sylvester equations over a multi-agent network with the constant step-size freely chosen from configurable intervals. Finally, the authors provide three examples to illustrate the effectiveness of the proposed algorithms.

Key words

Distributed optimization / least squares solution / linear convergence rate / step-size interval / Sylvester equation

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
CHENG Songsong , YU Xin , ZENG Xianlin , LIANG Shu , HONG Yiguang. Distributed Optimization and Scaling Design for Solving Sylvester Equations. Journal of Systems Science & Complexity, 2024, 37(6): 2487-2510 https://doi.org/10.1007/s11424-024-3407-6

References

[1] Li Z and Ding Z, Distributed optimization on unbalanced graphs via continuous-time methods, Science China Information Sciences, 2018, 61(12): 1-3.
[2] Wang Y, Zhao Y, and Zhang J F, Distributed recursive projection identification with binaryvalued observations, Journal of Systems Science & Complexity, 2021, 34(5): 2048-2068.
[3] Wang X, Wang G, and Li S, Distributed finite-time optimization for integrator chain multi-agent systems with disturbances, IEEE Trans. on Autom. Control, 2020, 65(12): 5296-5311.
[4] Zhao Q and Duan G R, Fully actuated system approach for 6DOF spacecraft control based on extended state observer, Journal of Systems Science & Complexity, 2022, 35(2): 604-622.
[5] Yu W, Li C, Yu X, et al., Economic power dispatch in smart grids: A framework for distributed optimization and consensus dynamics, Science China Information Sciences, 2018, 61(1): 1-16.
[6] Frihi Z E, Choutri S E, Barreiro-Gomez J, et al., Hierarchical mean-field type control of price dynamics for electricity in smart grid, Journal of Systems Science & Complexity, 2022, 35(1): 1-17.
[7] Yang T, Yi X, Wu J, et al., A survey of distributed optimization, Annual Reviews in Control, 2019, 47: 278-305.
[8] Wang Y, Tu Z, and Qin H, Distributed communication-sliding mirror-descent algorithm for nonsmooth resource allocation problem, Journal of Systems Science & Complexity, 2022, 35(4): 1244-1261.
[9] Ma X, Yi P, and Chen J, Distributed gradient tracking methods with finite data rates, Journal of Systems Science & Complexity, 2021, 34(5): 1927-1952.
[10] Wang D, Fang X, Wan Y, et al., Distributed event triggered optimization algorithm design for mass with attacks on communication edges, the 59th IEEE Conference on Decision and Control, 2020, 6150-6155.
[11] Zhang J and You K, AsySPA: An exact asynchronous algorithm for convex optimization over digraphs, IEEE Trans. on Autom. Control, 2019, 65(6): 2494-2509.
[12] Liu Q and Wang J, A second-order multi-agent network for bound-constrained distributed optimization, IEEE Trans. on Autom. Control, 2015, 60(12): 3310-3315.
[13] Qiu Z, Liu S, and Xie L, Distributed constrained optimal consensus of multi-agent systems, Automatica, 2016, 68: 209-215.
[14] Xu G H, Chen G P, and Qi H S, Algorithm design and approximation analysis on distributed robust game, Journal of Systems Science & Complexity, 2023, 36(2): 480-499.
[15] Lu D, Sun Y, and Wang D, A new algorithm for computing the extended Hensel construction of multivariate polynomials, Journal of Systems Science & Complexity, 2018, 31(6): 1633-1646.
[16] Zhang Z and Zheng L, A complex varying-parameter convergent-differential neural-network for solving online time varying complex Sylvester equation, IEEE Transactions on Cybernetics, 2018, 49(10): 3627-3639.
[17] Wei Q, Dobigeon N, Tourneret J Y, et al., R-fuse: Robust fast fusion of multiband images based on solving a Sylvester equation, IEEE Signal Processing Letters, 2016, 23(11): 1632-1636.
[18] Hu H, Lin Z, Feng J, et al., Smooth representation clustering, 2014 IEEE Conference on Computer Vision and Pattern Recognition, 2014, 3834-3841.
[19] Wang L, Li D, He T, et al., Manifold regularized multi-view subspace clustering for image representation, the 23rd International Conference on Pattern Recognition, 2016, 283-288.
[20] Shaker H R and Tahavori M, Control configuration selection for bilinear systems via generalised Hankel interaction index array, International Journal of Control, 2015, 88(1): 30-37.
[21] Xu X and Dubljevic S, Output and error feedback regulator designs for linear infinite-dimensional systems, Automatica, 2017, 83: 170-178.
[22] Golub G, Nash S, and Van Loan C, A Hessenberg-Schur method for the problem AX +XB = C, IEEE Trans. on Autom. Control, 1979, 24(6): 909-913.
[23] Benner P and Kürschner P, Computing real low-rank solutions of Sylvester equations by the factored ADI method, Computers & Mathematics with Applications, 2014, 67(9): 1656-1672.
[24] Hu D Y and Reichel L, Krylov-subspace methods for the Sylvester equation, Linear Algebra and Its Applications, 1992, 172: 283-313.
[25] Granat R and Kagström B, Parallel solvers for Sylvester-type matrix equations with applications in condition estimation, Part I: Theory and algorithms, ACM Transactions on Mathematical Software, 2010, 37(3): 1-32.
[26] Andersson P, Granat R, Jonsson I, et al., Parallel algorithms for triangular periodic Sylvester-type matrix equations, European Conference on Parallel Processing, 2008, 780-789.
[27] Wang P, Mou S, Lian J, et al., Solving a system of linear equations: From centralized to distributed algorithms, Annual Reviews in Control, 2019, 47: 306-322.
[28] Deng W, Li W, Zeng X, et al., A survey of distributed algorithms for solving matrix equations, Control Theory & Applications, 2021, 38(11): 1695-1706.
[29] Mou S, Liu J, and Morse A S, A distributed algorithm for solving a linear algebraic equation, IEEE Trans. on Autom. Control, 2015, 60(11): 2863-2878.
[30] Anderson B, Mou S, Morse A S, et al., Decentralized gradient algorithm for solution of a linear equation, 2016, arXiv: 1509.04538.
[31] Liu J, Mou S, and Morse A S, Asynchronous distributed algorithms for solving linear algebraic equations, IEEE Trans. on Autom. Control, 2017, 63(2): 372-385.
[32] Shi G, Anderson B D, and Helmke U, Network flows that solve linear equations, IEEE Trans. on Autom. Control, 2017, 62(6): 2659-2674.
[33] Yang T, George J, Qin J, et al., Distributed least squares solver for network linear equations, Automatica, 2020, 113: 108798.
[34] Zeng X, Liang S, Hong Y, et al., Distributed computation of linear matrix equations: An optimization perspective, IEEE Trans. on Autom. Control, 2018, 64(5): 1858-1873.
[35] Chen G, Zeng X, and Hong Y, Distributed optimisation design for solving the Stein equation with constraints, IET Control Theory & Applications, 2019, 13(15): 2492-2499.
[36] Deng W, Zeng X, and Hong Y, Distributed computation for solving the Sylvester equation based on optimization, IEEE Systems Control Letters, 2019, 4(2): 414-419.
[37] Deng W, Hong Y, Anderson B D, et al., Network flows that solve Sylvester matrix equations, IEEE Trans. on Autom. Control, 2022, 67(12): 6731-6738.
[38] Cao K, Zeng X, and Hong Y, Continuous-time distributed algorithms for solving linear algebraic equation, 36th Chinese Control Conference (CCC), 2017, 8068-8073.
[39] Liu J, Morse A S, Nedić A, et al., Exponential convergence of a distributed algorithm for solving linear algebraic equations, Automatica, 2017, 83: 37-46.
[40] Liu Y, Lageman C, Anderson B D, et al., An Arrow-Hurwicz-Uzawa type flow as least squares solver for network linear equations, Automatica, 2019, 100: 187-193.
[41] Ioffe A D, Variational Analysis of Regular Mappings: Theory and Applications. Springer International Publishing AG., Cham, Switzerland, 2017.
[42] Shi W, Ling Q, Wu G, et al., EXTRA: An exact first order algorithm for decentralized consensus optimization, SIAM Journal on Optimization, 2015, 25(2): 944-966.
[43] Golub G H and Van Loan C F, Matrix Computations, 2nd Edition, Johns Hopkins University Press, Baltimore, 1989.

Funding

This research was supported in part by the National Natural Science Foundation of China under Grant Nos. 62103003, 72171171, 62073035, 61973002, and in part by the Anhui Provincial Natural Science Foundation under Grant No. 2008085J32.
PDF(834 KB)

89

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉