مشکلات متمم در مدل GAMS و حل PATH

A fundamental mathematical problem is to find a solution to a square system of nonlinear equations. There are many methods to approach this problem, the most famous of which is Newton's method. In this paper, we describe a generalization of this problem, the complementarity problem. We show how such problems are modeled within the GAMS modeling language and provide details about the PATH solver, a generalization of Newton's method, for finding a solution. While the modeling format is applicable in many disciplines, we draw the examples in this paper from an economic background. Finally, some extensions of the modeling format and the solver are described.

Modeling languages are becoming increasingly important to application developers as the problems considered become more complex. Modeling languages such as AMPL or GAMS offer an environment tailored to expressing mathematical constructs. They can efficiently manage a large volume of data and allow users to concentrate on the model rather than the solution methodology. Over time, modeling languages have evolved and adapted as new algorithms and problem classes have been explored. A fundamental mathematical problem is to find a solution to a square system of nonlinear equations. Newton's method, perhaps the most famous solution technique, has been extensively used in practice to calculate a solution. Two generalizations of nonlinear equations are very popular with modelers, the constrained nonlinear system (that incorporates bounds on the variables), and the complementarity problem. The complementarity problem adds a combinatorial twist to the classic square system of nonlinear equations, thus enabling a broader range of situations to be modeled. For example, the complementarity problem can be used to model the Karush–Kuhn–Tucker (KKT) optimality conditions for nonlinear programs (Karush, 1939; Kuhn and Tucker, 1951), Wardropian and Walrasian equilibria (Ferris and Pang, 1997b), and bimatrix games (Lemke and Howson, 1964). One popular solver for these problems, PATH, is based upon a generalization of the classical Newton method. This method has achieved considerable success on practical problems. In this paper, we study the complementarity problem from a modeling perspective with emphasis on economic examples, show how to model such problems within the GAMS modeling language, and provide details about the PATH solver. We will assume an elementary understanding of linear programming, including basic duality theory, and a working knowledge of the GAMS modeling system (Brooke et al., 1988). We begin developing the complementarity framework by looking at the KKT conditions for linear programs. We discuss the adaptations made in GAMS to support the complementarity problem class and provide some additional examples. Section 3continues by elaborating on the PATH solver, available options, and output. Finally some extensions of the modeling format and additional uses of the solver are given.