留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

线性互补问题的数值分析

黎稳 郑华

黎稳, 郑华. 线性互补问题的数值分析[J]. 华南师范大学学报(自然科学版), 2015, 47(3): 1-0. doi: 10.6054/j.jscnun.2015.03.002
引用本文: 黎稳, 郑华. 线性互补问题的数值分析[J]. 华南师范大学学报(自然科学版), 2015, 47(3): 1-0. doi: 10.6054/j.jscnun.2015.03.002
LI Wen, Hua Zheng. Numerical Analysis on Linear Complementarity Problems[J]. Journal of South China normal University (Natural Science Edition), 2015, 47(3): 1-0. doi: 10.6054/j.jscnun.2015.03.002
Citation: LI Wen, Hua Zheng. Numerical Analysis on Linear Complementarity Problems[J]. Journal of South China normal University (Natural Science Edition), 2015, 47(3): 1-0. doi: 10.6054/j.jscnun.2015.03.002

线性互补问题的数值分析

doi: 10.6054/j.jscnun.2015.03.002
基金项目: 

国家自然科学基金;广东省高校创新基金

详细信息
    通讯作者:

    郑华

  • 中图分类号: O241.6

Numerical Analysis on Linear Complementarity Problems

More Information
    Corresponding author: Hua Zheng
  • 摘要: 综述了线性互补问题理论的最新发展和已有成果,包括线性互补问题的数值解法,特别是模基矩阵分析算法、误差分析以及扰动分析.给出了线性互补问题的数学问题形式、数学模型以及相关概念;介绍了求解线性互补问题的各种数值解法,其中重点关注迭代法特别是近年来比较热门的模基矩阵分裂迭代法,基于模方程通过运用非光滑 Newton 法的思想, 给出 了模基非光滑 Newton 法, 新算法比已 有的模基矩阵分裂迭代法收敛更快;给出了线性互补问 题解的误差分析,介绍了已有的几个误差界结果,包括运用 预处理技术得到的更好的新误差界.同时介绍了线性互补问题解扰动分析的结果及目前最新的扰动界.
  • [1] Berman A and Plemmons R J. Nonnegative Matrix in the Mathematical Sciences[M]. Philadelphia,SIAM Publisher, 1994.
    [2] Bai Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numer. Linear Algebra Appl., 2010(17): 917-933.
    [3] Bai Z Z. On the convergence of the multisplitting methods for the linear complementarity problem[J]. SIAM J. Matrix Anal. Appl. 1999(21): 67-78.
    [4] Bai Z Z and Evans D J. Matrix multisplitting methods with applications to linear complementarity problems: parallel synchronous and chaotic methods[J]. R$\acute{e}$seaux et Syst$\grave{e}$mes R$\acute{e}$partis: Calculateurs Parallel$\grave{e}$s, 2001(13): 125-154.
    [5] Bai Z Z, Sun J C and Wang D R. A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations[J]. Comput. Math. Appl., 1996(32): 51-76.
    [6] Bai Z Z and Zhang L L. Modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Numerical Linear Algebra Appl., 2013(20): 425-439.
    [7] Bai Z Z and Zhang L L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems[J]. Numerical Algorithms, 2013(62), 59-77.
    [8] Chen B. Error bounds for R0-type and monotone nonlinear complementarity problems[J]. J. Optim. Theory Appl. 2001(108): 297-316.
    [9] Chen T T, Li W, Wu X P and Vong S. Error bounds for linear complementarity problems of MB-matrices[J]. Numerical Algorithm, 2014, DOI 10.1007/s11075-014-9950-9.
    [10] Chen X J and Xiang S H. Computation of error bounds for P-matrix linear complementarity problems[J]. Math. Program. Ser. A, 2006(106): 513-525.
    [11] Chen X J and Xiang S H. Perturbation bounds for P-matrix linear complementarity problems[J]. SIAM J. Optim., 2007, 18(4): 1250-1265.
    [12] Clarke F H. Optimization and Nonsmooth Analysis[M]. New York, Wiley, 1983.
    [13] Cottle R W, Pang J S and Stone R E. The Linear Complementarity Problem[M], SanDiego, Academic, 1992.
    [14] Dai P F. Error bounds for linear complementarity problems of DB-matrices[J]. Linear Algebra Appl. 2011(434): 830-840.
    [15] Dai P F, Li Y T and Lu C J. New error bounds for linear complementarity problem with an SB-matrices[J]. Numer. Algor. 2013(64): 741-757.
    [16] Dong J L and Jiang M Q. A modified modulus method for symmetric positive-definite linear complementarity problems[J]. Numer. Linear Algebra Appl., 2009(16), 129-143.
    [17] Garcia-Esnaola M and Pena J M. A comparison of error bounds for linear complementarity problems of H-matrices[J]. Linear Algebra and its Applications, 2010(433): 956-964.
    [18] Goldstein A A. Convex programming in Hilbert space[J]. Bull Ame Math Soc, 1964(70), 709-710.
    [19] Frommer A and Szyld D B. H-splittings and two-stage iterative methods[J]. Numer. Math., 1992(63): 345-356.
    [20] Hadjidimos A and Tzoumas M. Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem[J]. Linear Algebra Appl., 2009(431): 197-210.
    [21] Levitin E S and Polyak B T. Constrained minimization methods[J]. Zh. Vychisl. Mat. Mat. Fiz., 1966, 6(5): 787-823.
    [22] Li H B, Huang T Z and Li H. On some subclasses of P-matrices[J]. Numer. Linear Algebra Appl. 2007(14): 391-405.
    [23] Li W. A general modulus-based matrix splitting method for linear complementarity problems of $H$- matrices[J]. Appl. Math. Lett. 2013(26): 1159-1164.
    [24] Li W and Zheng H. Some new error bounds for linear complementarity problems of H-matrices[J]. Numerical Algorithm, 2014(67): 257-269.
    [25] Li W and Zheng H. A preconditioned modulus-based iteration method for solving linear complementarity problems of H-matrices[J]. Linear and Multilinear Algebra, submitted.
    [26] Lim L H. Singular values and eigenvalues of tensors, A variational approach. in Proceedings 1st IEEE International Workshop on Computational Advances of Multitensor Adaptive processing, 2005: 129-132.
    [27] Mathias R and Pang J S. Error bounds for the linear complementarity problem with a P-matrix[J]. Linear Algebra Appl. 1990(132): 123-136.
    [28] MangasarianO L and Ren J. New improved error bounds for the linear complementarity problem[J]. Math. Programming 1994(66): 241-257.
    [29] Machida N, Fukushima M and Ibaraki T. A multisplitting method for symmetric linear complementarity problems[J]. J. Comput. Appl. Math., 1995(62): 217-227.
    [30] Murty K G. Linear Complementarity, Linear and Nonlinear Programming[M]. Berlin, Heldermann Verlag, 1988.
    [31] O.Leary D P and White R E. Multi-splittings of matrices and parallel solution of linear systems[J]. SIAM J. Algebraic Discrete Methods, 1985(6): 630-640.
    [32] Pang J S. Error bounds in mathematical programming[J]. Math. Programming, 1997(79): 299-332.
    [33] Qi L Q and Sun J. A nonsmooth version of Newton’s method[J]. Mathematical Programming, 1993(58): 353-367.
    [34] Qi L Q. Eigenvalues of a real supersymmetric tensor[J]. J. Symbolic Comput., 2005(40): 1302-1324.
    [35] Sch¨afer U. On the modulus algorithm for the linear complementarity problem[J]. Oper. Res. Lett., 2004(32): 350-354.
    [36] Song Y S and Qi L Q. Properties of tensor complementarity problem and some classes of structured tensors[J]. arXiv:1412.0113v1[math.OC].
    [37] Van BokhovenW M G. Piecewise-linear Modelling and Analysis[M]. Eindhoven, Proefschrift, 1981.
    [38] Yoshise A. Complementarity Problems[M]. In: Terlaky T, ed. Interior Point Methods of Mathematical Programming. Dordrecht: Kluwer Acamemic Publishers, 1996.
    [39] Zhang L L. Two-step modulus based matrix splitting iteration for linear complementarity problems[J]. Numer. Algorithms, 2011(57): 83-99.
    [40] Zhang L L. Two-stage multisplitting iteration methods using modulus-based matrix splitting as inner iteration for linear complementarity problems[J]. J. Optim. Theory Appl., 2014, 160(1): 189-203.
    [41] Zhang L L. Two-step modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Journal of Computational Mathematics, 2015, 33(1), 100-112.
    [42] Zheng H and Li W. The modulus-based nonsmooth Newton’s method for solving linear complementarity problems[J]. Journal of Computational and Applied Mathematics, submitted.
    [43] Zhang L L and Ren Z R. Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems[J], Applied Mathematicics Letters, 2013(26): 638-642.
    [44] 韩继业等. 非线性互补理论与算法[M]. 上海:上海科学技术出版社, 2006.
    [45] 张丽丽. 关于线性互补问题的模系矩阵分裂迭代方法[J]. 计算数学, 2012, 34(4):373-386.

    [1] Berman A and Plemmons R J. Nonnegative Matrix in the Mathematical Sciences[M]. Philadelphia,SIAM Publisher, 1994.
    [2] Bai Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numer. Linear Algebra Appl., 2010(17): 917-933.
    [3] Bai Z Z. On the convergence of the multisplitting methods for the linear complementarity problem[J]. SIAM J. Matrix Anal. Appl. 1999(21): 67-78.
    [4] Bai Z Z and Evans D J. Matrix multisplitting methods with applications to linear complementarity problems: parallel synchronous and chaotic methods[J]. R$\acute{e}$seaux et Syst$\grave{e}$mes R$\acute{e}$partis: Calculateurs Parallel$\grave{e}$s, 2001(13): 125-154.
    [5] Bai Z Z, Sun J C and Wang D R. A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations[J]. Comput. Math. Appl., 1996(32): 51-76.
    [6] Bai Z Z and Zhang L L. Modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Numerical Linear Algebra Appl., 2013(20): 425-439.
    [7] Bai Z Z and Zhang L L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems[J]. Numerical Algorithms, 2013(62), 59-77.
    [8] Chen B. Error bounds for R0-type and monotone nonlinear complementarity problems[J]. J. Optim. Theory Appl. 2001(108): 297-316.
    [9] Chen T T, Li W, Wu X P and Vong S. Error bounds for linear complementarity problems of MB-matrices[J]. Numerical Algorithm, 2014, DOI 10.1007/s11075-014-9950-9.
    [10] Chen X J and Xiang S H. Computation of error bounds for P-matrix linear complementarity problems[J]. Math. Program. Ser. A, 2006(106): 513-525.
    [11] Chen X J and Xiang S H. Perturbation bounds for P-matrix linear complementarity problems[J]. SIAM J. Optim., 2007, 18(4): 1250-1265.
    [12] Clarke F H. Optimization and Nonsmooth Analysis[M]. New York, Wiley, 1983.
    [13] Cottle R W, Pang J S and Stone R E. The Linear Complementarity Problem[M], SanDiego, Academic, 1992.
    [14] Dai P F. Error bounds for linear complementarity problems of DB-matrices[J]. Linear Algebra Appl. 2011(434): 830-840.
    [15] Dai P F, Li Y T and Lu C J. New error bounds for linear complementarity problem with an SB-matrices[J]. Numer. Algor. 2013(64): 741-757.
    [16] Dong J L and Jiang M Q. A modified modulus method for symmetric positive-definite linear complementarity problems[J]. Numer. Linear Algebra Appl., 2009(16), 129-143.
    [17] Garcia-Esnaola M and Pena J M. A comparison of error bounds for linear complementarity problems of H-matrices[J]. Linear Algebra and its Applications, 2010(433): 956-964.
    [18] Goldstein A A. Convex programming in Hilbert space[J]. Bull Ame Math Soc, 1964(70), 709-710.
    [19] Frommer A and Szyld D B. H-splittings and two-stage iterative methods[J]. Numer. Math., 1992(63): 345-356.
    [20] Hadjidimos A and Tzoumas M. Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem[J]. Linear Algebra Appl., 2009(431): 197-210.
    [21] Levitin E S and Polyak B T. Constrained minimization methods[J]. Zh. Vychisl. Mat. Mat. Fiz., 1966, 6(5): 787-823.
    [22] Li H B, Huang T Z and Li H. On some subclasses of P-matrices[J]. Numer. Linear Algebra Appl. 2007(14): 391-405.
    [23] Li W. A general modulus-based matrix splitting method for linear complementarity problems of $H$- matrices[J]. Appl. Math. Lett. 2013(26): 1159-1164.
    [24] Li W and Zheng H. Some new error bounds for linear complementarity problems of H-matrices[J]. Numerical Algorithm, 2014(67): 257-269.
    [25] Li W and Zheng H. A preconditioned modulus-based iteration method for solving linear complementarity problems of H-matrices[J]. Linear and Multilinear Algebra, submitted.
    [26] Lim L H. Singular values and eigenvalues of tensors, A variational approach. in Proceedings 1st IEEE International Workshop on Computational Advances of Multitensor Adaptive processing, 2005: 129-132.
    [27] Mathias R and Pang J S. Error bounds for the linear complementarity problem with a P-matrix[J]. Linear Algebra Appl. 1990(132): 123-136.
    [28] MangasarianO L and Ren J. New improved error bounds for the linear complementarity problem[J]. Math. Programming 1994(66): 241-257.
    [29] Machida N, Fukushima M and Ibaraki T. A multisplitting method for symmetric linear complementarity problems[J]. J. Comput. Appl. Math., 1995(62): 217-227.
    [30] Murty K G. Linear Complementarity, Linear and Nonlinear Programming[M]. Berlin, Heldermann Verlag, 1988.
    [31] O.Leary D P and White R E. Multi-splittings of matrices and parallel solution of linear systems[J]. SIAM J. Algebraic Discrete Methods, 1985(6): 630-640.
    [32] Pang J S. Error bounds in mathematical programming[J]. Math. Programming, 1997(79): 299-332.
    [33] Qi L Q and Sun J. A nonsmooth version of Newton’s method[J]. Mathematical Programming, 1993(58): 353-367.
    [34] Qi L Q. Eigenvalues of a real supersymmetric tensor[J]. J. Symbolic Comput., 2005(40): 1302-1324.
    [35] Sch¨afer U. On the modulus algorithm for the linear complementarity problem[J]. Oper. Res. Lett., 2004(32): 350-354.
    [36] Song Y S and Qi L Q. Properties of tensor complementarity problem and some classes of structured tensors[J]. arXiv:1412.0113v1[math.OC].
    [37] Van BokhovenW M G. Piecewise-linear Modelling and Analysis[M]. Eindhoven, Proefschrift, 1981.
    [38] Yoshise A. Complementarity Problems[M]. In: Terlaky T, ed. Interior Point Methods of Mathematical Programming. Dordrecht: Kluwer Acamemic Publishers, 1996.
    [39] Zhang L L. Two-step modulus based matrix splitting iteration for linear complementarity problems[J]. Numer. Algorithms, 2011(57): 83-99.
    [40] Zhang L L. Two-stage multisplitting iteration methods using modulus-based matrix splitting as inner iteration for linear complementarity problems[J]. J. Optim. Theory Appl., 2014, 160(1): 189-203.
    [41] Zhang L L. Two-step modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Journal of Computational Mathematics, 2015, 33(1), 100-112.
    [42] Zheng H and Li W. The modulus-based nonsmooth Newton’s method for solving linear complementarity problems[J]. Journal of Computational and Applied Mathematics, submitted.
    [43] Zhang L L and Ren Z R. Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems[J], Applied Mathematicics Letters, 2013(26): 638-642.
    [44] 韩继业等. 非线性互补理论与算法[M]. 上海:上海科学技术出版社, 2006.
    [45] 张丽丽. 关于线性互补问题的模系矩阵分裂迭代方法[J]. 计算数学, 2012, 34(4):373-386.
  • 加载中
计量
  • 文章访问数:  1150
  • HTML全文浏览量:  111
  • PDF下载量:  339
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-02-14
  • 修回日期:  2015-03-10
  • 刊出日期:  2015-05-25

目录

    /

    返回文章
    返回