Optimization Online


Exact computation of an error bound for a generalized linear complementarity problem with unique solution

Jean-Pierre Dussault(Jean-Pierre.Dussault***at***Usherbrooke.ca)
Jean Charles Gilbert(Jean-Charles.Gilbert***at***inria.fr)

Abstract: This paper considers a generalized form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a satisfactory upper estimate of that factor in terms of the data bitlength when the data is formed of rational numbers. Along the way, we show that, when any rowwise convex combination of two square matrices is nonsingular, the $\ell_\infty$ norm of the inverse of these rowwise convex combinations is maximized by an extreme diagonal matrix.

Keywords: Complexity, Data bitlength, Error bound, Extreme diagonal matrix, Linear complementarity problem, Matrix inverse norm, P-matrix, Rowwise convex combination of matrices, Separable function, Strong duality.

Category 1: Complementarity and Variational Inequalities

Citation: http://hal.inria.fr/hal-03389023/document

Download: [PDF]

Entry Submitted: 10/20/2021
Entry Accepted: 10/20/2021
Entry Last Modified: 10/20/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society