Advanced Search
Article Contents
Article Contents

An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems

  • * Corresponding author: C.-Y. Shi

    * Corresponding author: C.-Y. Shi 

This research is funded by The Science and Technology Development Fund, Macau SAR (File no. 0005/2019/A) and the grant MYRG2018-00047-FST, MYRG2017-00098-FST from University of Macau

Abstract Full Text(HTML) Figure(1) / Table(3) Related Papers Cited by
  • Many kinds of practical problems can be formulated as nonlinear complementarity problems. In this paper, an inexact alternating direction method of multipliers for the solution of a kind of nonlinear complementarity problems is proposed. The convergence analysis of the method is given. Numerical results confirm the theoretical analysis, and show that the proposed method can be more efficient and faster than the modulus-based Jacobi, Gauss-Seidel and Successive Overrelaxation method when the dimension of the problem being solved is large.

    Mathematics Subject Classification: 90C33, 65F10, 65F50, 65G40.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Porous Flow Through a Dam

    Table 1.  Numerical results of Example 1

    m Algorithm 1 MJ MGS MSOR
    $ 2^3 $ IT 57 170 83 81
    CPU 1.98E-03 1.35E-03 6.49E-04 6.82E-04
    RES 9.72E-07 9.86E-07 9.58E-07 8.21E-07
    $ 2^4 $ IT 106 644 272 270
    CPU 1.16E-02 1.62E-02 7.74E-03 7.14E-03
    RES 9.78E-07 9.98E-07 9.25E-07 9.97E-07
    $ 2^5 $ IT 210 2531 1131 865
    CPU 7.13E-02 1.36E-01 6.66E-02 5.05E-02
    RES 9.84E-07 9.98E-07 9.88E-07 9.89E-07
    $ 2^6 $ IT 435 4839 4729
    CPU 0.613 0.981 1.033
    RES 9.80E-07 9.99E-07 9.97E-07
    $ 2^7 $ IT 900
    CPU 5.57
    RES 9.96E-07
    $ 2^8 $ IT 1875
    CPU 75.5
    RES 9.99E-07
     | Show Table
    DownLoad: CSV

    Table 2.  Numerical results of Example 2

    M Algorithm 1 MJ MGS MSOR
    4 IT 82 925 365 308
    CPU 5.80E-03 7.80E-03 3.40E-03 2.90E-03
    RES 8.99E-07 9.97E-07 9.76E-07 9.56E-07
    5 IT 157 3862 1578 1203
    CPU 4.95E-02 1.15E-01 5.34E-02 4.14E-02
    RES 9.95E-07 9.99E-07 9.93E-07 9.94E-07
    6 IT 310 7536 7402
    CPU 0.370 0.976 0.972
    RES 9.99E-07 1.00E-06 9.97E-07
    7 IT 622
    CPU 3.52
    RES 9.99E-07
    8 IT 1255
    CPU 43.2
    RES 1.00E-06
    9 IT 2551
    CPU 584
    RES 9.98E-07
     | Show Table
    DownLoad: CSV

    Table 3.  Numerical results of Example 3

    M Algorithm 1 MJ MGS MSOR
    3 IT 337 730 311 307
    CPU 3.90E-02 1.09E-02 5.10E-03 4.90E-03
    RES 9.56E-07 9.91E-07 9.91E-07 9.46E-07
    4 IT 345 3039 1201 1031
    CPU 1.58E-01 1.37E-01 6.55E-02 5.25E-02
    RES 9.95E-07 9.96E-07 9.87E-07 9.97E-07
    5 IT 481 5610 4569
    CPU 0.861 1.13 1.02
    RES 9.89E-07 9.99E-07 9.96E-07
    6 IT 993
    CPU 8.80
    RES 1.00E-06
    7 IT 2069
    CPU 117
    RES 9.97E-07
    8 IT 4340
    CPU 1519
    RES 9.95E-07
     | Show Table
    DownLoad: CSV
  • [1] Z. Z. Bai, New comparison theorem for the nonlinear multisplitting relaxation method for the nonlinear complementarity problems, Comput. Math. Appl., 32 (1996), 41-48.  doi: 10.1016/0898-1221(96)00123-X.
    [2] Z. Z. Bai, A class of asynchronous parallel nonlinear accelerated over relaxation methods for the nonlinear complementarity problem, J. Comput. Appl. Math., 93 (1998), 35-44.  doi: 10.1016/S0377-0427(98)00280-5.
    [3] Z. Z. Bai, Asynchronous parallel nonlinear multisplitting relaxation methods for the large sparse nonlinear complementarity problems, Appl. Math. Comput., 92 (1998), 85-100.  doi: 10.1016/S0096-3003(97)10020-0.
    [4] Z. Z. BaiV. MigallónJ. Penadés and D. B. Szyld, Block and asynchronous two-stage methods for mildly nonlinear systems, Numer. Math., 82 (1999), 1-20.  doi: 10.1007/s002110050409.
    [5] S. Q. Du and Y. Gao, Merit functions for nonsmooth complementarity problems and related descent algorithm, Applied Mathematics - A Journal of Chinese Universities, 25 (2010), 78-84.  doi: 10.1007/s11766-010-2190-4.
    [6] W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66 (2016), 889-916.  doi: 10.1007/s10915-015-0048-x.
    [7] C. M. Elliott and J. R. Ockendon, Weak and variational methods for moving boundary problems, in Research Notes in Mathematics, 59, Pitman, Boston, London, 1982.
    [8] M. C. Ferris and C. Kanzow, Complementarity and related problems: A survey, in Handbook of Applied Optimization(eds. P. M. Pardalos, and M. G. C. Resende), Oxford University Press, New York, (2002), 514–530. doi: 10.1007/978-1-4757-5362-2.
    [9] M. C. Ferris, O. Mangasarian and J. Pang, Complementarity: Applications, Algorithms and Extensions, Springer, New York, 2011.
    [10] R. Glowinski and A. Marrocco, Sur l'approximation par éléments finis d'ordre un et la résolution par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires, Laboria Report 115, 1975.
    [11] K. H. Hoffmann and J. Zou, Parallel solution of variational inequality problems with nonlinear source terms, IMA J. Numer. Anal., 16 (1996), 31-45.  doi: 10.1093/imanum/16.1.31.
    [12] N. Huang and C. F. Ma, The modulus-based matrix splitting algorithms for a class of weakly nonlinear complementarity problems, Numer. Linear Algebra Appl., 23 (2016), 558-569.  doi: 10.1002/nla.2039.
    [13] P. T. Harker and J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Math. Program., 48 (1990), 161-220.  doi: 10.1007/BF01582255.
    [14] C. E. Lemke and J. T. Howson, Equilibrium points of bimatrix games, SIAM J. Appl. Math., 12 (1964), 413-423. 
    [15] R. Li and J. F. Yin, Accelerated modulus-based matrix splitting iteration methods for a restricted class of nonlinear complementarity problems, Numer. Algor., 75 (2017), 339-358.  doi: 10.1007/s11075-016-0243-3.
    [16] W. Li and W. W. Sun, Modified Gauss-Seidel type methods and Jacobi type methods for Z matrices, Linear Algebra Appl., 317 (2000), 227-240.  doi: 10.1016/S0024-3795(00)00140-3.
    [17] W. Li, A general modulus-based matrix splitting method for linear complementarity problems of H-matrices, Appl. Math. Lett., 26 (2013), 1159-1164.  doi: 10.1016/j.aml.2013.06.015.
    [18] C. F. Ma and N. Huang, Modified modulus-based matrix splitting algorithms for a class of weakly nondifferentiable nonlinear complementarity problems, Appl. Numer. Math., 108 (2016), 116-124.  doi: 10.1016/j.apnum.2016.05.004.
    [19] G. H. Meyer, Free boundary problems with nonlinear source terms, Numer. Math., 43 (1984), 463-482.  doi: 10.1007/BF01390185.
    [20] M. A. Noor, Fixed point approach for complementarity problems, J. Comput. Appl. Math., 133 (1988), 437-448.  doi: 10.1016/0022-247X(88)90413-1.
    [21] F. A. Potra and S. J. Wright, Interior-point methods, J. Comput. Appl. Math., 124 (2000), 255-281.  doi: 10.1016/S0377-0427(00)00433-7.
    [22] L. QiD. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Program., 87 (2000), 1-35.  doi: 10.1007/s101079900127.
    [23] Z. Sun and J. P. Zeng, A monotone semismooth Newton type method for a class of complementarity problems, J. Comput. Appl. Math., 235 (2011), 1261-1274.  doi: 10.1016/j.cam.2010.08.012.
    [24] M. Tao and X. Yuan, On Glowinski's open question on the alternating direction method of multipliers, Journal of Optimization Theory and Applications, 179 (2018), 163–196.
    [25] N. H. Xiu and J. Zhang, Some recent advances in projection-type methods for variational inequalities, J. Comput. Appl. Math., 152 (2003), 559-585.  doi: 10.1016/S0377-0427(02)00730-6.
    [26] S. L. XieH. R. Xu and J. P. Zeng, Two-step modulus-based matrix splitting iteration method for a class of nonlinear complementarity problems, Linear Algebra Appl., 494 (2016), 1-10.  doi: 10.1016/j.laa.2016.01.002.
    [27] Z. Xia and C. Li, Modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problem, Appl. Math. Comput., 271 (2015), 34-42. doi: 10.1016/j.amc.2015.08.108.
    [28] L. Yong, Nonlinear complementarity problem and solution methods, in Proceedings of the 2010 International Conference on Artificial Intelligence and Computational Intelligence, Part I, Springer-Verlag, (2010), 461–469.
    [29] H. ZhengS. Vong and L. Liu, The relaxation modulus-based matrix splitting iteration method for solving a class of nonlinear complementarity problems, Int. J. Comput. Math., 96 (2018), 1648-1667.  doi: 10.1080/00207160.2018.1504928.
    [30] H. Zheng and S. Vong, The modulus-based nonsmooth Newtons method for solving a class of nonlinear complementarity problems of P-matrices, Calcolo, 55 (2018), 37. doi: 10.1007/s10092-018-0279-y.
    [31] H. ZhengS. Vong and L. Liu, A direct preconditioned modulus-based iteration method for solving nonlinear complementarity problems of H-matrices, Appl. Math. Comput., 353 (2019), 396-405.  doi: 10.1016/j.amc.2019.02.015.
    [32] J. J. Zhang, MSSOR-based alternating direction method for symmetric positive-definite linear complementarity problems, Numer. Algor., 68 (2015), 631-644.  doi: 10.1007/s11075-014-9864-6.
    [33] J. J. ZhangJ. L. Zhang and W. Z. Ye, An inexact alternating direction method of multipliers for the solution of linear complementarity problems arising from free boundary problems, Numer. Algor., 78 (2018), 895-910.  doi: 10.1007/s11075-017-0405-y.
  • 加载中




Article Metrics

HTML views(1383) PDF downloads(405) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint