Smooth methods of multipliers for complementarity problems

This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs of monotone operators is de veloped and then applied to the monotone complementarity problem, obtaining primal, dual. and primal-dual formulations. We derive Bregman-function-bas ed generalized proximal algorithms for each of these formulations, generati ng three classes of complementarity algorithms. The primal class is well-kn own. The dual class is new and constitutes a general collection of methods of multipliers, or augmented Lagrangian methods, for complementarity proble ms. In a special case, it corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function, th e augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods is entirely new and combi nes the best theoretical features of the primal and dual methods. Some prel iminary computation shows that this class of algorithms is effective at sol ving many of the standard complementarity test problems.