Kybernetika 54 no. 3, 542-556, 2018

Multi-agent network flows that solve linear complementarity problems

Shu Liang and Xianlin ZengDOI: 10.14736/kyb-2018-3-0542

Abstract:

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.

Keywords:

linear complementarity problem, multi-agent network, distributed algorithm, nonsmooth algorithm, continuous-time algorithm

Classification:

90C33, 68W15

paper.pdf

References:

  1. J. P. Aubin and A. Cellina: Differential Inclusions. Springer-Verlag, Berlin 1984.   DOI:10.1007/978-3-642-69512-4
  2. A. Cherukuri and J. Cortés: 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
  3. J.-L. Dong, J. Gao, F. Ju and J. Shen: Modulus methods for nonnegatively constrained image restoration. SIAM J. Imaging Sci. 9 (2016), 1226-1246.   DOI:10.1137/15m1045892
  4. Y. Elfoutayeni and M. Khaladi: Using vector divisions in solving the linear complementarity problem. J. Comput. Appl. Math. 236 (2012), 1919-1925.   DOI:10.1016/j.cam.2011.11.001
  5. M. Herceg, C. N. Jones, M. Kvasnica and M. Morari: Enumeration-based approach to solving parametric linear complementarity problems. Automatica 62 (2015), 243-248.   DOI:10.1016/j.automatica.2015.09.019
  6. M.-C. Hu, S.-Y. Lu and Y.-H. Chen: 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. D. T. K. Huyen and N. D. Yen: Coderivatives and the solution map of a linear constraint system. SIAM J. Optim. 26 (2016), 986-1007.   DOI:10.1137/140998469
  8. H. K. Khalil: Nonlinear Systems. Third edition. Prentice Hall, New Jersey, 2002.   CrossRef
  9. S. Liang, P. Yi and Y. Hong: Distributed {N}ash equilibrium seeking for aggregative games with coupled constraints. Automatica 85 (2017), 179-185.   DOI:10.1016/j.automatica.2017.07.064
  10. C. Liu and C. Li: 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
  11. J. Liu, A. S. Morse, A. Nedić and T. Basar: Exponential convergence of a distributed algorithm for solving linear algebraic equations. Automatica 83 (2017), 37-46.   DOI:10.1016/j.automatica.2017.05.004
  12. Q. Liu, S. Yang and J. Wang: A collective neurodynamic approach to distributed constrained optimization. IEEE Trans. Neural Networks Learning Systems 28 (2017), 1747-1758.   DOI:10.1109/tnnls.2016.2549566
  13. Y. Lou, Y. Hong and S. Wang: Distributed continuous-time approximate projection protocols for shortest distance optimization problems. Automatica 69 (2016), 289-297.   DOI:10.1016/j.automatica.2016.02.019
  14. S. Mei, W. Wei and F. Liu: On engineering game theory with its application in power systems. Control Theory Technol. 15 (2017), 1-12.   DOI:10.1007/s11768-017-6186-y
  15. H. S. Najafi and S. Edalatpanah: 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
  16. H. Peng, F. Li, S. Zhang and B. Chen: 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. M. Posa, C. Cantu and R. Tedrake: A direct method for trajectory optimization of rigid bodies through contact. Int. J. Robotics Res. 33 (2014), 69-81.   DOI:10.1177/0278364913506757
  18. P. V. Reddy and G. Zaccour: Feedback {N}ash equilibria in linear-quadratic difference games with constraints. IEEE Trans. Automat. Control 62 (2017), 590-604.   DOI:10.1109/tac.2016.2555879
  19. R. W. Cottle, Jong-Shi Pang and R. E. Stone: The Linear Complementarity Problem. SIAM, Commonwealth of Pennsylvania, 2009.   DOI:10.1137/1.9780898719000
  20. R. T. Rockafellar and R. J. B. Wets: Variational Analysis. Springer-Verlag, New York, 1998.   DOI:10.1007/978-3-642-02431-3
  21. V. Sessa, L. Iannelli and F. Vasca: A complementarity model for closed-loop power converters. IEEE Trans. Power Electron. 29 (2014), 6821-6835.   DOI:10.1109/tpel.2014.2306975
  22. G. Shi, B. D. O. Anderson and U. Helmke: Network flows that solve linear equations. IEEE Trans. Automat. Control 62 (2017), 2659-2674.   DOI:10.1109/tac.2016.2612819
  23. E. M. Simantiraki and D. F. Shanno: An infeasible-interior-point method for linear complementarity problems. SIAM J. Optim. 7 (1997), 620-640.   DOI:10.1137/s1052623495282882
  24. R. Tonge, F. Benevolenski and A. Voroshilov: Mass splitting for jitter-free parallel rigid body simulation. ACM Trans. Graphics 31 (2012), 4, 1-8.   DOI:10.1145/2185520.2185601
  25. Y. Wang, P. Lin and Y. Hong: Distributed regression estimation with incomplete data in multi-agent networks. Science China Inform. Sci. 61 (2018), 092202.   DOI:10.1007/s11432-016-9173-8
  26. Y. Xie and U. V. Shanbhag: On robust solutions to uncertain linear complementarity problems and their variants. SIAM J. Optim. 26 (2016), 2120-2159.   DOI:10.1137/15m1010427
  27. P. Xu, E. Cannon and G. Lachapelle: Stabilizing ill-conditioned linear complementarity problems. J. Geodesy 73 (1999), 204-213.   DOI:10.1007/s001900050237
  28. J. Yao, I. Adler and S. S. Oren: Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network. Oper. Res. 56 (2008), 34-47.   DOI:10.1287/opre.1070.0416
  29. P. Yi, Y. Hong and F. Liu: 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
  30. X. Zeng and K. Cao: Computation of linear algebraic equations with solvability verification over multi-agent networks. Kybernetika 53 (2017), 803-819.   DOI:10.14736/kyb-2017-5-0803
  31. X. Zeng, S. Liang, Y. Hong and J. Chen: 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. 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