%A Steven P. Dirkse
%T Robust Solution of Mixed Complementarity Problems
%D August 1994
%R 94-12
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X This thesis is concerned with algorithms and software for the solution
of the Mixed Complementarity Problem, or MCP. The MCP formulation is
useful for expressing systems of nonlinear inequalities and equations;
the complementarity allows boundary conditions be to specified in a
succinct manner. Problems of this type occur in many branches of the
sciences, including mathematics, engineering, economics, operations
research, and computer science.
The algorithm we propose for the solution of MCP is a Newton based
method containing a novel application of a nonmonotone stabilization
technique previously applied to methods for solving smooth systems of
equalities and for unconstrained minimization. In order to apply this
technique, we have adapted and extended the path construction
technique of \citeasnoun{ralph:global}, resulting in the PATH
algorithm. We present a global convergence result for the PATH
algorithm that generalizes similar results obtained in the smooth
case. The PATH solver is a sophisticated implementation of this
algorithm that makes use of the sparse basis updating package of MINOS
5.4.
Due to the widespread use of algebraic modeling languages in the
practice of operations research, economics, and other fields from
which complementarity problems are drawn, we have developed a
complementarity facility for both the GAMS and AMPL modeling
languages, as well as software interface libraries to be used in
hooking up a complementarity solver as a solution subsystem. These
interface libraries provide the algorithm developer with a convenient
and efficient means of developing and testing an algorithm, while also
benefiting the modeling community by providing ready access to the
latest advances in algorithmic development.
The library interface routines are used to read a number of
complementarity models formulated in the GAMS and AMPL modeling
languages. We define the syntax required for these models and
describe their derivation. These models have been collected to form a
library and have been made publicly available so that others may
benefit from this work.
We present extensive computational results for the PATH solver and
other solution techniques, many of which are obtained by using the
interface library and the library of complementarity models developed
for this purpose.