Algorithms for Complementarity Problems and Generalized Equations

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 arbitrary starting points. Using the MCPLIB and GAMSLIB test libraries, we perform extensive computational tests that demonstrate the effectiveness 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 Pang & Gabriel (1993), the semismooth equations approach of De Luca, Facchinei & Kanzow (1995), and the infeasible-interior point method of Wright (1994) are all generalized to the mixed complementarity problems framework. In addition, the pivotal method of Cao & Ferris (1995b), which solves affine variational inequalities, is extended to solve affine generalized equations. To develop this extension, the piecewise-linear homotopy framework of Eaves (1976) is used to generate an algorithm finds a solution in a finite number of iterations under the assumption that the piecewise affine map is coherently oriented.