zbMATH — the first resource for mathematics

Complementarity problems in GAMS and the PATH solver. (English) Zbl 1002.90070
Summary: 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.
Reviewer: Reviewer (Berlin)

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
Full Text: DOI
[1] Billups, S.C.; Dirkse, S.P.; Ferris, M.C., A comparison of large scale mixed complementarity problem solvers, Computational optimization and applications, 7, 3-25, (1997) · Zbl 0883.90116
[2] Billups, S.C.; Ferris, M.C., QPCOMP: a quadratic program based solver for mixed complementarity problems, Mathematical programming, 76, 533-562, (1997) · Zbl 0873.90095
[3] Brooke, A., Kendrick, D., Meeraus, A., 1988. GAMS: A User’s Guide. The Scientific Press, South San Francisco, CA.
[4] Chamberlain, R.M.; Powell, M.J.D.; LemarĂ©chal, C., The watchdog technique for forcing convergence in algorithms for constrained optimization, Mathematical programming study, 16, 1-17, (1982) · Zbl 0477.90072
[5] Cottle, R.W.; Dantzig, G.B., Complementary pivot theory of mathematical programming, Linear algebra and its applications, 1, 103-125, (1968) · Zbl 0155.28403
[6] Cottle, R.W., Pang, J.S., Stone, R.E., 1992. The Linear Complementarity Problem. Academic Press, Boston. · Zbl 0757.90078
[7] Dirkse, S.P.; Ferris, M.C., MCPLIB: a collection of nonlinear mixed complementarity problems, Optimization methods and software, 5, 319-345, (1995)
[8] Dirkse, S.P.; Ferris, M.C., The PATH solver: a non-monotone stabilization scheme for mixed complementarity problems, Optimization methods and software, 5, 123-156, (1995)
[9] Dirkse, S.P., Ferris, M.C., 1996. A pathsearch damped Newton method for computing general equilibria. Annals of Operations Research, 68, 211-232. · Zbl 0868.90012
[10] Dirkse, S.P., Ferris, M.C., 1997. Crash techniques for large-scale complementarity problems. In: Ferris, M.C., Pang, J.S. (Eds.), Complementarity and Variational Problems: State of the Art. SIAM Publications, Philadelphia, PA. pp. 40-61. · Zbl 0886.90150
[11] Dirkse, S.P., Ferris, M.C., 1998a. Modeling and solution environments for MPEC: GAMS & MATLAB. In: Fukushima, M., Qi, L. (Eds.), Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic, Dordrecht, 1999, pp. 127-148. · Zbl 0927.65082
[12] Dirkse, S.P., Ferris, M.C., 1998b. Traffic modeling and variational inequalities using GAMS. In: Toint, P.L., Labbe, M., Tanczos, K., Laporte, G. (Eds.), Operations Research and Decision Aid Methodologies in Traffic and Transportation Management, NATO ASI Series F., Springer, Berlin.
[13] Dirkse, S.P., Ferris, M.C., Preckel, P.V., Rutherford, T., 1994. The GAMS callable program library for variational and complementarity solvers. Mathematical Programming Technical Report 94-07, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin.
[14] Ferris, M.C., Horn, J.D., 1998. NLP2MCP: Automatic conversion of nonlinear programs into mixed complementarity problems. Technical Report, Computer Sciences Department, University of Wisconsin. In preparation.
[15] Ferris, M.C., Kanzow, C., Munson, T.S., 1998a. Feasible descent algorithms for mixed complementarity problems. Mathematical Programming, forthcoming. · Zbl 0946.90094
[16] Ferris, M.C.; Lucidi, S., Nonmonotone stabilization methods for nonlinear equations, Journal of optimization theory and applications, 81, 53-71, (1994) · Zbl 0803.65070
[17] Ferris, M.C., Meeraus, A., Rutherford, T.F., 1998b. Computing Wardropian equilibrium in a complementarity framework. Optimization Methods and Software, forthcoming. · Zbl 0938.90006
[18] Ferris, M.C., Munson, T.S., 1998a. Case studies in complementarity: improving model formulation. Mathematical Programming Technical Report 98-16, Computer Sciences Department, University of Wisconsin, Madison, WI. · Zbl 0946.90093
[19] Ferris, M.C., Munson, T.S., 1998b. Interfaces to PATH 3.0: design, implementation and usage. Computational Optimization and Applications, forthcoming. · Zbl 1040.90549
[20] Ferris, M.C., Pang, J.S. (Eds.), 1997a. Complementarity and Variational Problems: State of the Art. SIAM Publications, Philadelphia, PA.
[21] Ferris, M.C.; Pang, J.S., Engineering and economic applications of complementarity problems, SIAM review, 39, 669-713, (1997) · Zbl 0891.90158
[22] Fischer, A., A special Newton-type optimization method, Optimization, 24, 269-284, (1992) · Zbl 0814.65063
[23] Harker, P.T.; Pang, J.S., Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Mathematical programming, 48, 161-220, (1990) · Zbl 0734.90098
[24] Harrison, G.W., Rutherford, T.F., Tarr, D., 1997. Quantifying the Uruguay round. Economic Journal 107, 1405-1430.
[25] Josephy, N.H., 1979. Newton’s method for generalized equations. Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin, Madison, WI.
[26] Karush, W., 1939. Minima of functions of several variables with inequalities as side conditions. Master’s Thesis, Department of Mathematics, University of Chicago.
[27] Kuhn, H.W., Tucker, A.W., 1951. Nonlinear programming. In: Neyman, J. (Ed.), Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley and Los Angeles, pp. 481-492. · Zbl 0044.05903
[28] Lemke, C.E.; Howson, J.T., Equilibrium points of bimatrix games, SIAM journal on applied mathematics, 12, 413-423, (1964) · Zbl 0128.14804
[29] Luo, Z.-Q., Pang, J.S., Ralph, D., 1996. Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge.
[30] Mathiesen, L., Computation of economic equilibria by a sequence of linear complementarity problems, Mathematical programming study, 23, 144-162, (1985) · Zbl 0579.90093
[31] Mathiesen, L., An algorithm based on a sequence of linear complementarity problems applied to a Walrasian equilibrium model: an example, Mathematical programming, 37, 1-18, (1987) · Zbl 0613.90098
[32] Outrata, J.V.; Zowe, J., A numerical approach to optimization problems with variational inequality constraints, Mathematical programming, 68, 105-130, (1995) · Zbl 0835.90093
[33] Ralph, D., Global convergence of damped Newton’s method for nonsmooth equations, via the path search, Mathematics of operations research, 19, 352-389, (1994) · Zbl 0819.90102
[34] Robinson, S.M., Normal maps induced by linear transformations, Mathematics of operations research, 17, 691-714, (1992) · Zbl 0777.90063
[35] Robinson, S.M., Newton’s method for a class of nonsmooth functions, Set valued analysis, 2, 291-305, (1994) · Zbl 0804.65062
[36] Rutherford, T.F., Extensions of GAMS for complementarity problems arising in applied economic analysis, Journal of economic dynamics and control, 19, 1299-1324, (1995) · Zbl 0877.90074
[37] Rutherford, T.F., 1998. Applied general equilibrium modeling with MPSGE as a GAMS subsystem: an overview of the modeling framework and syntax. Computational Economics, forthcoming. · Zbl 0951.91037
[38] Schneider, M.H.; Zenios, S.A., A comparative study of algorithms for matrix balancing, Operations research, 38, 439-455, (1990) · Zbl 0703.90094
[39] Schramm, H.; Zowe, J., A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM journal on optimization, 2, 121-152, (1992) · Zbl 0761.90090
[40] Stackelberg, H.V., 1952. The Theory of Market Economy. Oxford University Press, Oxford.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.