%A Stephen C. Billups %T Algorithms for Complementarity Problems and Generalized Equations %D August 7, 1995 %R 95-14 %I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN %C MADISON, WI %X ABSTRACT Recent improvements in the capabilities of complementarity solvers have led to an increased interest in using the complementarity problem framework to address practical problems arising in mathematical programming, economics, engineering, and the sciences. As a result, increasingly more difficult problems are being proposed that exceed the capabilities of even the best algorithms currently available. There is, therefore, an immediate need to improve the capabilities of complementarity solvers. This thesis addresses this need in two significant ways. First, the thesis proposes and develops a proximal perturbation strategy that enhances the robustness of Newton-based complementarity solvers. This strategy enables algorithms to reliably find solutions even for problems whose natural merit functions have strict local minima that are not solutions. Based upon this strategy, three new algorithms are proposed for solving nonlinear mixed complementarity problems that represent a significant improvement in robustness over previous algorithms. These algorithms have local Q-quadratic convergence behavior, yet depend only on a pseudo-monotonicity assumption to achieve global convergence from arbitrary starting points. Using the MCPLIB and GAMSLIB test libraries, we perform extensive computational tests that demonstrate the effectiveness of these algorithms on realistic problems. Second, the thesis extends some previously existing algorithms to solve more general problem classes. Specifically, the NE/SQP method of \citeasnoun{pang.gabriel:nesqp}, the semismooth equations approach of \citeasnoun{deluca.facchinei.ea:semismooth}, and the infeasible-interior point method of \citeasnoun{wright:infeasible-interior-point} are all generalized to the mixed complementarity problem framework. In addition, the pivotal method of \citeasnoun{cao.ferris:pivotal}, which solves affine variational inequalities, is extended to solve affine generalized equations. To develop this extension, the piecewise-linear homotopy framework of \citeasnoun{eaves:short} is used to generate an algorithm for finding zeros of piecewise affine maps. We show that the resulting algorithm finds a solution in a finite number of iterations under the assumption that the piecewise affine map is coherently oriented.