Algorithms and Environments for Complementarity

Abstract

Complementarity problems arise in a wide variety of disciplines. Prototypical examples include theWardropian andWalrasian equilibrium models encountered in the engineering and economic disciplines and the first order optimality conditions for nonlinear programs from the optimization community. The main focus of this thesis is algorithms and environments for solving complementarity problems. Environments, such as AMPL and GAMS, are used by practitioners to easily write large, complex models. Support for these packages is provided by PATH 4.x and SEMI through the customizable solver interface specified in this thesis. The main design feature is the abstraction of core components from the code with implementations tailored to a particular environment supplied either at compile or run time. This solver interface is then used to develop new links to the MATLAB and NEOS tools. Preprocessing techniques are an integral part of linear and mixed integer programming codes and are primarily used to reduce the size and complexity of a model prior to solving it. For example, wasted computation is avoided when an infeasible model is detected. This thesis documents the new techniques for preprocessing complementarity problems contained in the PATH 4.x and SEMI algorithms. PATH 4.x is more reliable than prior versions of the code and has been able to find solutions to previously unsolvable models. The reasons for the improvement are discussed in this thesis and include new theoretical developments for a globalization scheme based on the Fischer-Burmeister merit function, and enhancements made to the linear complementarity solver, nonmonotone linesearch, and restart strategy. SEMI is an alternative to PATH 4.x based on the semismooth algorithm. The main ii computation in PATH 4.x is to solve linear complementarity problems, which can be quite expensive. The new SEMI code described in this thesis only solves linear systems of equations and uses iterative methods to process very large models. The theme of this thesis is ?enabling? technologies in complementarity: environments enable practitioners to easily specify models; sophisticated codes enable them to solve the models; and theory assures them that the algorithm is well-defined and efficiently processes models.