Smooth methods of multipliers for complementarity problems |
| |
Authors: | Jonathan Eckstein Michael C Ferris |
| |
Institution: | (1) Faculty of Management and RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854, e-mail: jeckstei@rutcor.rutgers.edu., US;(2) University of Wisconsin, Computer Sciences Department, 1210 West Dayton Street, Madison, WI 53706, e-mail: ferris@cs.wisc.edu., US |
| |
Abstract: | This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs
of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual
formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating
three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general
collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it
corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function,
the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods
is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows
that this class of algorithms is effective at solving many of the standard complementarity test problems.
Received February 21, 1997 / Revised version received December 11, 1998? Published online May 12, 1999 |
| |
Keywords: | : complementarity problems – smoothing – proximal algorithms – augmented Lagrangians |
本文献已被 SpringerLink 等数据库收录! |
|