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