Error bounds for monotone linear complementarity problems

We give a bound on the distance between an arbitrary point and the solution set of a monotone linear complementarity problem in terms of a condition constant that depends on the problem data only and a residual function of the violations of the complementary problem conditions by the point considered. When the point satisfies the linear inequalities of the complementarity problem, the residual consists of the complementarity condition plus its square root. This latter term is essential and without it the error bound cannot hold. We also show that another natural residual that has been employed to bound errors for strictly monotone linear complementarity problems fails to bound errors for the monotone case considered here. Sponsored by the United States Army under contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Foundation Grant DCR-8420963 and Air Force Office of Scientific Research Grant AFOSR-ISSA-85-00080.     

Error bounds for nondegenerate monotone linear complementarity problems

Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which all solutions are degenerate. Thus when a point satisfies the linear inequalities of a nondegenerate complementarity problem, the residual that bounds the distance from a solution point consists of the complementarity condition alone, whereas for degenerate problems this residual cannot bound the distance to a solution without adding the square root of the complementarity condition to it. This and other simplified results are a consequence of the polyhedral characterization of the solution set as the intersection of the feasible region {zMz + q 0, z 0} with a single linear affine inequality constraint.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

Error bounds for linear complementarity problems of S-QN matrices

Numerical Algorithms - It is well-known that conjugate gradient algorithms are widely applied in many practical fields, for instance, engineering problems and finance models, as they are...     

Error bounds for linear complementarity problems of Nekrasov matrices

We present error bounds for the linear complementarity problem when the involved matrix is a Nekrasov matrix and also when it is a \(\Sigma \) -Nekrasov matrix. The new bounds can improve considerably other previous bounds.     

Error bounds for linear complementarity problems of DB-matrices

Doubly B-matrices (DB-matrices), which properly contain B-matrices, are introduced by Peña (2003) [2]. In this paper we present error bounds for the linear complementarity problem when the matrix involved is a DB-matrix and a new bound for linear complementarity problem of a B-matrix. The numerical examples show that the bounds are sharp.     

B-Nekrasov matrices and error bounds for linear complementarity problems

The class of B-Nekrasov matrices is a subclass of P-matrices that contains Nekrasov Z-matrices with positive diagonal entries as well as B-matrices. Error bounds for the linear complementarity problem when the involved matrix is a B-Nekrasov matrix are presented. Numerical examples show the sharpness and applicability of the bounds.     

Some new error bounds for linear complementarity problems of H-matrices

Some new error bounds for linear complementarity problems of H-matrices are presented based on the preconditioned technique. Numerical examples show that these bounds are better than some existing ones.     

Note on error bounds for linear complementarity problems of Nekrasov matrices

Numerical Algorithms - García-Esnaola and Peña (Numer. Algor. 67, 655–667, 2014) presented an error bound involving a parameter for linear complementarity problems of Nekrasov...     

Solution of linear complementarity problems using minimization with simple bounds

We define a minimization problem with simple bounds associated to the horizontal linear complementarity problem (HLCP). When the HLCP is solvable, its solutions are the global minimizers of the associated problem. When the HLCP is feasible, we are able to prove a number of properties of the stationary points of the associated problem. In many cases, the stationary points are solutions of the HLCP. The theoretical results allow us to conjecture that local methods for box constrained optimization applied to the associated problem are efficient tools for solving linear complementarity problems. Numerical experiments seem to confirm this conjecture.This work was supported by FAPESP (grants 90-3724-6 and 91-2441-3), CNPq and FAEP (UNICAMP).     

On the asymptotic optimality of error bounds for some linear complementarity problems

Numerical Algorithms - We introduce strong B-matrices and strong B-Nekrasov matrices, for which some error bounds for linear complementarity problems are analyzed. In particular, it is proved that...     

An improvement of the error bounds for linear complementarity problems of Nekrasov matrices

A new error bound for the linear complementarity problems, which involves a parameter, is given when the involved matrices are Nekrasov matrices. It is shown that there exists an optimal value of the parameter such that the new bound is sharper than that provided by Li et al. (Numer Algor. 2017;74:997–1009). Numerical examples are given to illustrate the corresponding results.     

A comparison of error bounds for linear complementarity problems of H-matrices

We give new error bounds for the linear complementarity problem when the involved matrix is an H-matrix with positive diagonals. We find classes of H-matrices for which the new bounds improve considerably other previous bounds. We also show advantages of these new bounds with respect the computational cost. A new perturbation bound of H-matrices linear complementarity problems is also presented.     

关于B-Nekrasov矩阵线性互补问题最优误差界的注记

研究了B-Nekrasov矩阵线性互补问题的含有参数误差界的最优值问题,利用函数的单调性,在_0_(i_1)···_n···_(i_(n-1))≥0且0_n1的情况下,得到了该误差界的最优值.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

Newton's method for linear complementarity problems

This paper presents an iterative, Newton-type method for solving a class of linear complementarity problems. This class was discovered by Mangasarian who had established that these problems can be solved as linear programs. Cottle and Pang characterized solutions of the problems in terms of least elements of certain polyhedral sets. The algorithms developed in this paper are shown to converge to the least element solutions. Some applications and computational results are also discussed.     

New improved error bounds for the linear complementarity problem

New local and global error bounds are given for both nonmonotone and monotone linear complementarity problems. Comparisons of various residuals used in these error bounds are given. A possible candidate for a best error bound emerges from our comparisons as the sum of two natural residuals.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.