A copositive Q-matrix which is notR 0

Jeter and Pye gave an example to show that Pang's conjecture, thatL ₁ ?Q ?R ₀, is false while Seetharama Gowda showed that the conjecture is true for symmetric matrices. It is known thatL ₁-symmetric matrices are copositive matrices. Jeter and Pye as well as Seetharama Gowda raised the following question: Is it trueC ₀ ?Q ?R ₀? In this note we present an example of a copositive Q-matrix which is notR ₀. The example is based on the following elementary proposition: LetA be a square matrix of ordern. SupposeR ₁ =R ₂ whereR _i stands for theith row ofA. Further supposeA ₁₁ andA ₂₂ are Q-matrices whereA _ii stands for the principal submatrix omitting theith row andith column fromA. ThenA is a Q-matrix.     

Identification of the Optimal Active Set in a Noninterior Continuation Method for LCP

This paper concerns about the possibility of identifying the active set in a noninterior continuation method for solving the standard linear complementarity problem based on the algorithm and theory presented by Burke and Xu (J. Optim. Theory Appl. 112 (2002) 53). It is shown that under the assumptions of P-matrix and nondegeneracy, the algorithm requires at most Olog(₀₀/)) iterations to find the optimal active set, where ₀ is the width of the neighborhood which depends on the initial point, ₀> 0 is the initial smoothing parameter, is a positive number which depends on the problem and the initial point, and is a small positive number which depends only on the problem.     

The P-matrix problem is co-NP-complete

Recently Rohn and Poljak proved that for interval matrices with rank-one radius matrices testing singularity is NP-complete. This paper will show that given any matrix family belonging to the class of matrix polytopes with hypercube domains and rank-one perturbation matrices, a class which contains the interval matrices, testing singularity reduces to testing whether a certain matrix is not a P-matrix. It follows from this result that the problem of testing whether a given matrix is a P-matrix is co-NP-complete.     

A note on a quadratic formulation for linear complementarity problems

In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known.     

Error Estimation for Nonlinear Complementarity Problems via Linear Systems with Interval Data

For the nonlinear complementarity problem, we derive norm bounds for the error of an approximate solution, generalizing the known results for the linear case. Furthermore, we present a linear system with interval data, whose solution set contains the error of an approximate solution. We perform extensive numerical tests and compare the different approaches.     

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.     

与P矩阵和LCP有关的量(英文)

发展了与P矩阵有关的基本量的一些新性质,并且改进了由Xiu和Zhang[A characteristic quantity ofP-matrices,Appl.Math.Lett.,2002,15:41-46]提出的水平线性余问题全局误差上限.     

A new method for a class of linear variational inequalities

In this paper we introduce a new iterative scheme for the numerical solution of a class of linear variational inequalities. Each iteration of the method consists essentially only of a projection to a closed convex set and two matrix-vector multiplications. Both the method and the convergence proof are very simple.This work is supported by the National Natural Science Foundation of the P.R. China and NSF of Jiangsu.     

A note on sufficient conditions forQ 0 andQ 0 ⋂P 0 matrices

In this note we settle an open problem posed by Al-Khayyal on a condition being sufficient for a matrix to belong to the class ofQ ₀-matrices. The answer is in the affirmative and we further relax the condition and obtain a sufficient condition forQ ₀-matrices. The results yield a class of matrices for which the linear complementarity problems can be solved as simple linear programs.     

A constructive characterization ofQ o-matrices with nonnegative principal minors

In [2] we characterized the class of matrices with nonnegative principla minors for which the linear-complementarity problem always has a solution. That class is contained in the one we study here. Our main result gives a finitely testable set of necessary and sufficient conditions under which a matrix with nonnegative principal minors has the property that if a corresponding linear complementarity problem is feasible then it is solvable. In short, we constructively characterize the matrix class known asQ _o ∩P _o . Research partially supported by the National Science Foundation Grant DMS-8420623 and U.S. Department of Energy Contract DE-AA03-76SF00326, PA # DE-AS03-76ER72018.     

A Smoothing Method for a Mathematical Program with P-Matrix Linear Complementarity Constraints

We consider a mathematical program whose constraints involve a parametric P-matrix linear complementarity problem with the design (upper level) variables as parameters. Solutions of this complementarity problem define a piecewise linear function of the parameters. We study a smoothing function of this function for solving the mathematical program. We investigate the limiting behaviour of optimal solutions, KKT points and B-stationary points of the smoothing problem. We show that a class of mathematical programs with P-matrix linear complementarity constraints can be reformulated as a piecewise convex program and solved through a sequence of continuously differentiable convex programs. Preliminary numerical results indicate that the method and convex reformulation are promising.     

线性互补问题的一种新Lagrange乘子法

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. Based on the Lagrangian of LCP(q,M) introduced here, we construct a new differentiable merit function θ(x,λ) which containing a multiplier vector λ and satisfying θ(x,λ) ≥ 0 and θ(x,λ) = 0 if and if only x solves LCP(q,M). A simple damped Newton-type algorithm which based on the merit function θ(x,λ) is presented. The main feature of the method is that the multiplier self-adjusting step accelerates the local convergence rate without losing global convergence. When M is the P-matrix, the sequence {θ(x^k,λ^k)}where {(x^k,λ^k)} generated by the algorithm is globally linearly convergent to zero and convergent in finite number of iterations if the solution is nondegenerate. Numerical results suggest that the method is high efficient and promising.     

线性互补问题的阻尼牛顿法的有限终止性

在（２）中，Ｈａｒｋｅｒ和Ｐａｎｇ提出了如下一个公开问题，对于线性互补问题的阻尼牛顿算法，当它收敛时，算法是否能在有限步内终止？本文对此问题给出一个肯定回答，而且进一步给出一个新的求解一般线性互补问题的有限终止算法，这个算法避免了阻尼牛顿算法可能不收敛的情形。     

On a “stability” in the linear complementarity problem

In this work we re-wrote the Linear Complementarity Problem in a formulation based on unknown projector operators. In particular, this formulation allows the introduction of a concept of “stability” that, in a certain way, might explain the way block pivotal algorithm performs.     

A new pivoting algorithm for the linear complementarity problem allowing for an arbitrary starting point

The linear complementarity problem is to find nonnegative vectors which are affinely related and complementary. In this paper we propose a new complementary pivoting algorithm for solving the linear complementarity problem as a more efficient alternative to the algorithms proposed by Lemke and by Talman and Van der Heyden. The algorithm can start at an arbitrary nonnegative vector and converges under the same conditions as Lemke's algorithm.This research is part of the VF-program Competition and Cooperation.     

A note on economic equilibrium and financial networks

Nagurney （1999） used variational inequalities to study economic equilibrium and financial networks and applied the modified projection method to solve the problem. In this paper, we formulate the problem as a nonlinear complementarity problem. The complementarity model is just the KKT condition for the model of Nagurney （1999）. It is a simpler model than that of Nagurney （1999）. We also establish sufficient conditions for existence and uniqueness of the equilibrium pattern, which are weaker than those in Nagurney （]999）. Finally, we apply a smoothing Newton-type algorithm to solve the problem and report some numerical results.