Error Bounds For The Linear Complementarity Problem Of Special Matrices

Abstract:The linear complementarity problem is a fundamental problem in the study of optimization theory and methodology,which grows up in the 1960s.The linear complementarity problems are closely related to linear programming,quadratic programming,bimatrix games,optimization theory,variational inequalities,equilibrium problems,game theory,fixed point theory and other mathematical branches,so these issues have attracted the attention of many scholars at home and abroad,and they researched them intensively.They have made great achievements in the study of theories and algorithms.However,there are errors between the real solution and the numerical solution obtained by different algorithms for linear complementarity problem,so it is necessary to analyze the error bounds.Therefore,the error bounds estimation for linear complementarity problem has become one of the current research hotspots.In this paper,some new error bounds for the linear complementarity problem are obtained when the involved matrix is a B-matrix,B~S-matrix or B-S-Nekrasov matrix,which are more accurate and easy to calculate.Meanwhile,we also carry on discussion and numerical verification to these estimation formulas.In Chapter 1,we briefly describe the background and significance of the dissertation,some basic concepts and lemmas which are used in this dissertation and the main work about this dissertation.In Chapter 2,some error bounds for linear complementarity problem of B-matrices are presented.Based on the range for the infinity norm of inverse matrix of a strictly diagonally dominant M-matrix,some new error bounds for the linear complementarity problem are obtained when the involved matrix is a B-matrix.Theory analysis and numerical examples show that these bounds improve existed results.In Chapter 3,some error bounds for linear complementarity problem of B~S-matrices are presented.Based on the range for the infinity norm of inverse matrix of a strictly diagonally dominant M-matrix,some new error bounds for the linear complementarity problem are obtained when the involved matrix is a B~S-matrix.Theory analysis and numerical examples show that these bounds improve existed results.In Chapter 4,some estimation formulas of error bound for linear complementarity problem of B-S-Nekrasov matrices are presented.Based on the range for the infinity norm of inverse matrix of a S-Nekrasov matrix,some new error bounds for the linear complementarity problem are obtained when the involved matrix is a S-Nekrasovmatrix.Based on the obtained results,we also give a new error bound for linear complementarity problem of B-S-Nekrasov matrices.In Chapter 5,we summarize our results and point out the future prospects of research work.