ROBUST SOLUTION OF MIXED COMPLEMENTARITY PROBLEMS

Abstract

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 Ralph (1994), 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.