In this note, we develop some new properties of a fundamental quantity associated with a P-matrix introduced by Mathias and Pang[1]. Also, based on extensions of such a quantity, we obtain global error bounds for the vertical and horizontal linear complementarity problems.

We propose a noninterior continuation method for the monotone linear complementarity problem (LCP) by modifying the Burke-Xu framework of the noninterior predictor-corrector path-following method (Refs. 1-2). The new method solves one system of linear equations and carries out only one line search at each iteration. It is shown to converge to the LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution. Our analysis of the continuation method is based on a broader class of the smooth functions introduced by Chen and Mangasarian (Ref. 3).

Projection-type methods are a class of simple methods for solving variational inequalities, especially for complementarity problems.In this paper we review and summarize recent developments in this class of methods, and focus mainly on some new trends in projection-type methods.

A noninterior continuation method is proposed for nonlinear complementarity problems. It improves the noninterior continuation methods recently studied by Burke and Xu [Math. Oper. Res., 23 (1998), pp. 719{734} and Xu [The Global Linear Convergence of an Infeasible Non-Interior Path-following Algorithm for Complementarity Problems with Uniform P-functions, Preprint, Department of Mathematics, University of Washington, Seattle, 1996]; the interior point neighborhood technique is extended to a broader class of smoothing functions introduced by Chen and Mangasarian [Comput. Optim. Appl., 5 (1996), pp. 97{138}. The method is shown to be globally linearly convergent following the methodology established by Burke and Xu. In addition, a local acceleration step is added to the method so that it is also locally quadratically convergent under suitable assumptions.

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 O (ρ log (β0μ0/τ)) iterations to find the optimal active set, where β0 is the width of the neighborhood which depends on the initial point, μ0 > 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.