New error bound for linear complementarity problems for B-matrices

A new error bound for the linear complementarity problem is obtained when the involved matrix is a B-matrix. This bound improves existing results. Finally, two numerical examples are also given to show that the bound is better than some previous results.     

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.     

On the extended linear complementarity problem

For the extended linear complementarity problem (Mangasarian and Pang, 1995), we introduce and characterize column-sufficiency, row-sufficiency andP-properties. These properties are then specialized to the vertical, horizontal and mixed linear complementarity problems. This paper is dedicated to Professor Olvi L. Mangasarian on the occasion of his 60th birthday.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

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 perturbation bounds of the linear complementarity problem

In this paper, new perturbation bounds for linear complementarity problems are presented based on the sign patterns of the solution of the equivalent modulus equations. The new bounds are shown to be the generalization of the existing ones.     

A note on solvability of a class of linear complementarity problems

We give a characterization of unique solvability of an infinite family of linear complementarity problems of a special form by means of a finite subset of this family.     

Solving more linear complementarity problems with Murty's bard-type algorithm

The linear complementarity problem (M|q) is to findw andz inR ⁿ such thatw–Mz=q,w0,z0,w ^t z=0, givenM inR ^n×n andq in . Murty's Bard-type algorithm for solving LCP is modeled as a digraph.Murty's original convergence proof considered allq inR ⁿ andM inR ^n×n , aP-matrix. We show how to solve more LCP's by restricting the set ofq vectors and enlarging the class ofM matrices beyondP-matrices. The effect is that the graph contains an embedded graph of the type considered by Stickney and Watson wheneverM is a matrix containing a principal submatrix which is aP-matrix. Examples are presented which show what can happen when the hypotheses are further weakened.     

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.     

Existence theorems of solution to variational inequality problems

This paper introduces a new concept of exceptional family for variational inequality problems with a general convex constrained set. By using this new concept, the authors establish a general sufficient condition for the existence of a solution to the problem. This condition is weaker than many known solution conditions and it is also necessary for pseudomonotone variational inequalities. Suffi-cient solution conditions for a class of nonlinear complementarity problems with Po mappings are also obtained.     

On general infinite dimensional complementarity problems

The aim of this paper is to present a way to study directly generalized complementarity problems in normed spaces. By means of new results on infinite dimensional Lagrange theory we show some optimality conditions which reduce the study of the problems to the one of suitable systems of equalities and inequalities.     

Structured backward error for palindromic polynomial eigenvalue problems,II: Approximate eigentriplets

A detailed structured backward error analysis for four kinds of palindromic polynomial eigenvalue problems (PPEPs)P(\lambda )\equiv \left({\displaystyle \sum _{l=\mathrm{0}}^d{{\displaystyle A}}_l{\lambda }^l}\right)x=\mathrm{0},{{\displaystyle A}}_{d-l}=\epsilon {{\displaystyle A}}_l^{★},L=\mathrm{0},\mathrm{1},\dots ,\left[{\displaystyle \frac{d}{\mathrm{2}}}\right], for an approximate eigentriplet is performed, where ★ is one of the two actions: transpose and conjugate transpose, and \epsilon \in \{\pm \mathrm{1}\}. The analysis is concerned with estimating the smallest perturbation to P(\lambda); while preserving the respective palindromic structure, such that the given approximate eigentriplet is an exact eigentriplet of the perturbed PPEP. Previously, R. Li, W. Lin, and C. Wang [Numer. Math., 2010, 116(1): 95–122] had only considered the case of an approximate eigenpair for PPEP but commented that attempt for an approximate eigentriplet was unsuccessful. Indeed, the latter case is much more complicated. We provide computable upper bounds for the structured backward errors. Our main results in this paper are several informative and very sharp upper bounds that are capable of revealing distinctive features of PPEP from general polynomial eigenvalue problems (PEPs). In particular, they reveal the critical cases in which there is no structured backward perturbation such that the given approximate eigentriplet becomes an exact one of any perturbed PPEP, unless further additional conditions are imposed. These critical cases turn out to the same as those from the earlier studies on an approximate eigenpair.     

On solutions of generalized complementarity and eigenvector problems

From a new Fan–Browder type fixed point theorem due to the second author, we deduce an existence theorem for a solution of an equilibrium problem in Section 3. This theorem is applied to generalized complementarity problems in Section 4 and to eigenvector problems in Section 5.     

On the modulus algorithm for the linear complementarity problem

Concerning three subclasses of P-matrices the modulus algorithm and the projected successive overrelaxation (PSOR) method solving the linear complementarity problem are compared to each other with respect to convergence. It is shown that the modulus algorithm is convergent for all three subclasses whereas the convergence of the PSOR method is only guaranteed for two of them.     

Error bounds of two smoothing approximations for semi-infinite minimax problems

In the paper we investigate smoothing method for solving semi-infinite minimax problems. Not like most of the literature in semi-infinite minimax problems which are concerned with the continuous time version（i.e., the one dimensional semi-infinite minimax problems）, the primary focus of this paper is on multi- dimensional semi-infinite minimax problems. The global error bounds of two smoothing approximations for the objective function are given and compared. It is proved that the smoothing approximation given in this paper can provide a better error bound than the existing one in literature.     

On computer-assisted proofs for solutions of linear complementarity problems

In this paper we consider the linear complementarity problem where the components of the input data M and q are not exactly known but can be enclosed in intervals. We compare three tests to each other each of which can be used by a computer that supports interval arithmetic to give guaranteed bounds for a solution of the LCP defined by M and q.     

Regularized gap functions and error bounds for split mixed vector quasivariational inequality problems

In this paper, we consider a class of split mixed vector quasivariational inequality problems in real Hilbert spaces and establish new gap functions by using the method of the nonlinear scalarization function. Further, we obtain some error bounds for the underlying split mixed vector quasivariational inequality problems in terms of regularized gap functions. Finally, we give some examples to illustrate our results. The results obtained in this paper are new.