Nonlinear complementarity problems (NCPs) arise in various fields of mathematics, natural sciences, engineering and economics. For example, we can think of Karush-Kuhn-Tucker conditions of nonlinear programs, discretized obstacle problems, the Wardrop principle for transportation networks, or Walrasian equilibrium models. Therefore, there is a growing interest in efficient and robust numerical methods for NCPs that are large or highly nonlinear.
We will first review several theoretical approaches for solving NCPs that make use of Newton’s linearization principle. Moreover, we will briefly describe corresponding numerical methods and report on existing software.
In a second part of the talk we will concentrate on one of the most popular approaches for solving NCPs. It is based on the reformulation of the NCP as a semismooth system of equations. The reformulation is done by means of so-called NCP-functions. Theoretical properties of the semismooth system and of algorithms for its solution as well as the practical performance of those algorithms depend on the NCP-function chosen. Therefore, we will discuss theoretical differences for some of these functions and highlight their numerical behavior within a Newton-type algorithm for solving the semismooth system within the GAMS modeling package.