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.

For the extended linear complementarity problem over an affine subspace, we first study some characterizations of (strong) column/row monotonicity and (strong) R0-property. We then establish global s-type error bound for this problem with the column monotonicity or R0-property, especially for the one with the nondegeneracy and column monotonicity, and give several equivalent formulations of such error bound without the square root term for monotone affine variational inequality. Finally, we use this error bound to derive some properties of the iterative sequence produced by smoothing methods for solving such a problem under suitable assumptions.

In this paper we develop the convergence theory of a general class of projection and contraction algorithms (PC method), where an extended stepsize rule is used, for solving variational inequality (VI) problems. It is shown that, by defining a scaled projection residue, the PC method forces the sequence of the residues to zero. It is also shown that, by defining a projected function, the PC method forces the sequence of projected functions to zero. A consequence of this result is that if the PC method converges to a nondegenerate solution of the VI problem, then after a finite number of iterations, the optimal face is identified. Finally, we study local convergence behavior of the extragradient algorithm for solving the KKT system of the inequality constrained VI problem.

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.

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).