Previous |  Up |  Next


distributed algorithm; linear complementarity problem; multi-agent network; nonsmooth algorithm; continuous-time algorithm
In this paper, we consider linear complementarity problems with positive definite matrices through a multi-agent network. We propose a distributed continuous-time algorithm and show its correctness and convergence. Moreover, with the help of Kalman-Yakubovich-Popov lemma and Lyapunov function, we prove its asymptotic convergence. We also present an alternative distributed algorithm in terms of an ordinary differential equation. Finally, we illustrate the effectiveness of our method by simulations.
[1] Aubin, J. P., Cellina, A.: Differential Inclusions. Springer-Verlag, Berlin 1984. DOI 10.1007/978-3-642-69512-4 | MR 0755330
[2] Cherukuri, A., Cortés, J.: Initialization-free distributed coordination for economic dispatch under varying loads and generator commitment. Automatica 74 (2016), 183-193. DOI 10.1016/j.automatica.2016.07.003 | MR 3569384
[3] Dong, J.-L., Gao, J., Ju, F., Shen, J.: Modulus methods for nonnegatively constrained image restoration. SIAM J. Imaging Sci. 9 (2016), 1226-1246. DOI 10.1137/15m1045892 | MR 3541995
[4] Elfoutayeni, Y., Khaladi, M.: Using vector divisions in solving the linear complementarity problem. J. Comput. Appl. Math. 236 (2012), 1919-1925. DOI 10.1016/ | MR 2863525
[5] Herceg, M., Jones, C. N., Kvasnica, M., Morari, M.: Enumeration-based approach to solving parametric linear complementarity problems. Automatica 62 (2015), 243-248. DOI 10.1016/j.automatica.2015.09.019 | MR 3423995
[6] Hu, M.-C., Lu, S.-Y., Chen, Y.-H.: Stochastic-multiobjective market equilibrium analysis of a demand response program in energy market under uncertainty. Appl. Energy 182 (2016), 500-506. DOI 10.1016/j.apenergy.2016.08.112
[7] Huyen, D. T. K., Yen, N. D.: Coderivatives and the solution map of a linear constraint system. SIAM J. Optim. 26 (2016), 986-1007. DOI 10.1137/140998469 | MR 3485978
[8] Khalil, H. K.: Nonlinear Systems. Third edition. Prentice Hall, New Jersey, 2002.
[9] Liang, S., Yi, P., Hong, Y.: Distributed {N}ash equilibrium seeking for aggregative games with coupled constraints. Automatica 85 (2017), 179-185. DOI 10.1016/j.automatica.2017.07.064 | MR 3712859
[10] Liu, C., Li, C.: Synchronous and asynchronous multisplitting iteration schemes for solving mixed linear complementarity problems with {H}-matrices. J. Optim. Theory Appl. 171 (2016), 169-185. DOI 10.1007/s10957-016-0944-8 | MR 3547848
[11] Liu, J., Morse, A. S., Nedić, A., Basar, T.: Exponential convergence of a distributed algorithm for solving linear algebraic equations. Automatica 83 (2017), 37-46. DOI 10.1016/j.automatica.2017.05.004 | MR 3680412
[12] Liu, Q., Yang, S., Wang, J.: A collective neurodynamic approach to distributed constrained optimization. IEEE Trans. Neural Networks Learning Systems 28 (2017), 1747-1758. DOI 10.1109/tnnls.2016.2549566 | MR 3684229
[13] Lou, Y., Hong, Y., Wang, S.: Distributed continuous-time approximate projection protocols for shortest distance optimization problems. Automatica 69 (2016), 289-297. DOI 10.1016/j.automatica.2016.02.019 | MR 3500113 | Zbl 1338.93026
[14] Mei, S., Wei, W., Liu, F.: On engineering game theory with its application in power systems. Control Theory Technol. 15 (2017), 1-12. DOI 10.1007/s11768-017-6186-y | MR 3598943
[15] Najafi, H. S., Edalatpanah, S.: On the convergence regions of generalized accelerated overrelaxation method for linear complementarity problems. J. Optim. Theory Appl. 156 (2013), 859-866. DOI 10.1007/s10957-012-0135-1 | MR 3022313
[16] Peng, H., Li, F., Zhang, S., Chen, B.: A novel fast model predictive control with actuator saturation for large-scale structures. Computers Structures 187 (2017), 35-49. DOI 10.1016/j.compstruc.2017.03.014
[17] Posa, M., Cantu, C., Tedrake, R.: A direct method for trajectory optimization of rigid bodies through contact. Int. J. Robotics Res. 33 (2014), 69-81. DOI 10.1177/0278364913506757
[18] Reddy, P. V., Zaccour, G.: Feedback Nash equilibria in linear-quadratic difference games with constraints. IEEE Trans. Automat. Control 62 (2017), 590-604. DOI 10.1109/tac.2016.2555879 | MR 3607165
[19] Cottle, R. W., Pang, Jong-Shi, Stone, R. E.: The Linear Complementarity Problem. SIAM, Commonwealth of Pennsylvania, 2009. DOI 10.1137/1.9780898719000
[20] Rockafellar, R. T., Wets, R. J. B.: Variational Analysis. Springer-Verlag, New York, 1998. DOI 10.1007/978-3-642-02431-3 | Zbl 0888.49001
[21] Sessa, V., Iannelli, L., Vasca, F.: A complementarity model for closed-loop power converters. IEEE Trans. Power Electron. 29 (2014), 6821-6835. DOI 10.1109/tpel.2014.2306975
[22] Shi, G., Anderson, B. D. O., Helmke, U.: Network flows that solve linear equations. IEEE Trans. Automat. Control 62 (2017), 2659-2674. DOI 10.1109/tac.2016.2612819 | MR 3660554
[23] Simantiraki, E. M., Shanno, D. F.: An infeasible-interior-point method for linear complementarity problems. SIAM J. Optim. 7 (1997), 620-640. DOI 10.1137/s1052623495282882 | MR 1462058
[24] Tonge, R., Benevolenski, F., Voroshilov, A.: Mass splitting for jitter-free parallel rigid body simulation. ACM Trans. Graphics 31 (2012), 4, 1-8. DOI 10.1145/2185520.2185601
[25] Wang, Y., Lin, P., Hong, Y.: Distributed regression estimation with incomplete data in multi-agent networks. Science China Inform. Sci. 61 (2018), 092202. DOI 10.1007/s11432-016-9173-8 | MR 3742944
[26] Xie, Y., Shanbhag, U. V.: On robust solutions to uncertain linear complementarity problems and their variants. SIAM J. Optim. 26 (2016), 2120-2159. DOI 10.1137/15m1010427 | MR 3561777
[27] Xu, P., Cannon, E., Lachapelle, G.: Stabilizing ill-conditioned linear complementarity problems. J. Geodesy 73 (1999), 204-213. DOI 10.1007/s001900050237
[28] Yao, J., Adler, I., Oren, S. S.: Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network. Oper. Res. 56 (2008), 34-47. DOI 10.1287/opre.1070.0416 | MR 2402216
[29] Yi, P., Hong, Y., Liu, F.: Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and its application to economic dispatch of power systems. Automatica 74 (2016), 259-269. DOI 10.1016/j.automatica.2016.08.007 | MR 3569392
[30] Zeng, X., Cao, K.: Computation of linear algebraic equations with solvability verification over multi-agent networks. Kybernetika 53 (2017), 803-819. DOI 10.14736/kyb-2017-5-0803 | MR 3750104
[31] Zeng, X., Liang, S., Hong, Y., Chen, J.: Distributed computation of linear matrix equations: an optimization perspective. IEEE Trans. Automat. Control, in press, arXiv preprint arXiv:1708.01833. DOI 10.1109/tac.2017.2752001
[32] 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 10.1109/tac.2016.2628807 | MR 3708893
Partner of
EuDML logo