×

A pathsearch damped Newton method for computing general equilibria. (English) Zbl 0868.90012

Summary: Computable general equilibrium models and other types of variational inequalities play a key role in computational economics. This paper describes the design and implementation of a pathsearch damped Newton method for solving such problems. Our algorithm improves on the typical Newton method (which generates and solves a sequence of LCPs) in both speed and robustness. The underlying complementarily problem is reformulated as a normal map so that standard algorithmic enhancements of Newton’s method for solving nonlinear equations can be easily applied. The solver is implemented as a GAMS subsystem, using an interface library developed for this purpose. Computational results obtained from a number of test problems arising in economics are given.

MSC:

91B50 General equilibrium theory
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K.M. Anstreicher, J. Lee and T.F. Rutherford, Crashing a maximum-weight complementarity basis, Mathematical Programming 54(1992)281–294. · Zbl 0764.90082 · doi:10.1007/BF01586055
[2] L. Armijo, Minimization of functions having Lipschitz-continuous first partial derivatives, Pacific Journal on Mathematics 16(1966)1–3. · Zbl 0202.46105
[3] A. Auslander, Convergence of stationary sequences for variational inequalities with maximal monotone operators, Applied Mathematics and Optimization 28(1993)161–172. · Zbl 0788.49014 · doi:10.1007/BF01182979
[4] A. Auslander and M. Haddou, An interior-proximal method for convex linearly constraints problems and its extension to variational inequalities, Technical Report, Université de Paris 1 and Laboratoire d’Econométrie de l’Ecole Polytechnique, Paris, 1994.
[5] C. Ballard, D. Fullerton, J. Shoven and J. Whalley,A General Equilibrium Model for the Tax Policy Evaluation, University of Chicago Press, 1984.
[6] R.M. Chamberlain, M.J.D. Powell and C. Lemaréchal, The watchdog technique for forcing convergence in algorithms for constrained optimization, Mathematical Programming Study 16(1982)1–17. · Zbl 0477.90072 · doi:10.1007/BFb0120945
[7] B. Chen and P.T. Harker, A non-interior continuation method for linear complementarity problems, SIAM Journal on Matrix Analysis 14(1993)1168–1190. · Zbl 0788.65073 · doi:10.1137/0614081
[8] B. Chen and P.T. Harker, A non-interior continuation method for monoton variational inequalities, Mathematical Programming (1994).
[9] C. Chen and O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Mathematical Programming Technical Report 94-11, Computer Sciences Department, University of Wisconsin, Madison, WI, 1994. Available from ftp: //ftp.cs.wisc.edu/math-prog/tech-reports/ · Zbl 0859.90112
[10] A.R. Colville, A comparative study on nonlinear programming codes, Technical Report 320-2949, IBM New York Scientific Center, 1968. · Zbl 0224.90069
[11] T. Condon, H. Dahl and S. Devarajan, Implementing a computable general equilibrium model on GAMS – the Cameroon model, DRD Discussion Paper 290, The World Bank, Washington, DC, 1987.
[12] S.P. Dirkse, Robust solution of mixed complementarity problems, Ph.D. Thesis, Computer Sciences Department, University of Wisconsin, Madison, WI, 1994. Available from ftp: //ftp.cs.wisc.edu/math-prog/tech-reports/
[13] S.P. Dirkse and M.C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems, Optimization Methods and Software. Available from ftp: //ftp.cs.wisc.edu/math-prog/tech-reports/
[14] S.P. Dirkse and M.C. Ferris, The PATH solver: A non-monotone stablization scheme for mixed complementarity problems, Optimization Methods and Software 4(1995).
[15] S.P. Dirkse, M.C. Ferris, P.V. Preckel and T. Rutherford, The GAMS callable program library for variational and complementarity solvers, Mathematical Programming Technical Report 94-07, Computer Sciences Department, University of Wisconsin, Madison, WI, 1994. Available from ftp: //ftp.cs.wisc.edu/math-prog/tech-reports/
[16] M.C. Ferris and S. Lucidi, Nonmonotone stabilization methods for nonlinear equations, Journal of Optimization Theory and Applications 81(1994)53–71. · Zbl 0803.65070 · doi:10.1007/BF02190313
[17] M.C. Ferris and D. Ralph, Projected gradient methods for nonlinear complementarity problems via normal maps, in:Recent Advances in Nonsmooth Optimization, D. Du, L. Qi and R. Womersley, eds., 1995. Available from ftp: //ftp.cs.wisc.edu/math-prog/tech-reports/ · Zbl 0946.90090
[18] R. Fourer, D.M. Gay and B.W. Kernighan,AMPL: A Modeling Language for Mathematical Programming, The Scientific Press, South San Francisco, CA, 1993. · Zbl 0701.90062
[19] M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Mathematical Programming 53 (1992)99–110. · Zbl 0756.90081 · doi:10.1007/BF01585696
[20] S.A. Gabriel and J.S. Pang, An inexact NE/SQP method for solving the nonlinear complementarity problem, Computational Optimization and Applications 1(1992)67–91. · Zbl 0794.90071 · doi:10.1007/BF00247654
[21] S.A. Gabriel and J.S. Pang, A trust region method for constrained nonsmooth equations, in:Large-Scale Optimization: State of the Art, W.W. Hager, D.W. Hearn and P.M. Pardalos, eds., Kluwer Academic, 1994, pp. 159–186.
[22] D.M. Gay, Hooking your solver to AMPL, Numerical Analysis Manuscript 93-10, AT&T Bell Laboratories, Murray Hill, NJ, 1993.
[23] L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton’s method, SIAM Journal of Numerical Analysis 23(1986)707–716. · Zbl 0616.65067 · doi:10.1137/0723046
[24] L. Grippo, F. Lampariello and S. Lucidi, A class of nonmonotone stabilization methods in unconstrained optimization, Numerische Mathematik 59(1991)779–805. · Zbl 0739.90062 · doi:10.1007/BF01385810
[25] O. Güler, Existence of interior points and interior paths in nonlinear monotone complementarity problems, Mathematics and Operations Research 18(1993)128–147. · Zbl 0816.90125 · doi:10.1287/moor.18.1.128
[26] P.T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms, and applications, Mathematical Programming 48(1990)161–220. · Zbl 0734.90098 · doi:10.1007/BF01582255
[27] P.T. Harker and B. Xiao, Newton’s method for the nonlinear complementarity problems: A B-differentiable equation approach, Mathematical Programming 48(1990)339–358. · Zbl 0724.90071 · doi:10.1007/BF01582262
[28] P.M.J. Harris, Pivot selection methods of the Devex LP code, Mathematical Programming 5(1973) 1–28. · Zbl 0261.90031 · doi:10.1007/BF01580108
[29] J.-B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms I, Vol. 305 ofGrundlehren der mathematischen Wissenschaften, Springer, Berlin, 1993.
[30] N.H. Josephy, Newton’s method for generalized equations, Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin-Madison, Madison, WI, 1979.
[31] C.Kanzow, Some equation-based methods for the nonlinear complementarity problem. Optimization Methods and Software 3(1994)327–340. · doi:10.1080/10556789408805573
[32] M. Kojima, N. Megiddo and T. Noma, Homotopy continuation methods for nonlinear complementarity problems, Mathematics of Operations Research 16(1991)754–774. · Zbl 0744.90087 · doi:10.1287/moor.16.4.754
[33] M. Kojima, N. Megiddo, T. Noma and A. Yoshise,A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Vol. 538 ofLecture Notes in Computer Science, Springer, Berlin, 1991. · Zbl 0745.90069
[34] M. Kojima, S. Mizono and T. Noma, A new continuation method for complementarity problems with uniform P-function, Mathematical Programming 43(1989)107–113. · Zbl 0673.90084 · doi:10.1007/BF01582283
[35] C.E. Lemke and J.T. Howson, Jr., Equilibrium points of bimatrix games, SIAM Journal of Applied Mathematics 2(1964)413–423. · Zbl 0128.14804 · doi:10.1137/0112033
[36] J.G. MacKinnon, A technique for the solution of spatial equilibrium models,Journal of Regional Science 16(1976)293–307. · doi:10.1111/j.1467-9787.1976.tb00976.x
[37] O.L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations, SIAM Journal of Applied Mathematics 31(1976)89–92. · Zbl 0339.90051 · doi:10.1137/0131009
[38] O.L. Mangasarian and M.V. Solodov, Nonlinear complementarity as unconstrained and constrained minimization. Mathematical Programming 62(1993)277–298. · Zbl 0813.90117 · doi:10.1007/BF01585171
[39] A.S. Manne, ETA-Macro: A model of energy-economy interactions, in:Modeling Energy-Economy Interactions, C.J. Hitch, ed., Resources for the Future, Washington, DC, 1977.
[40] L. Mathiesen, An algorithm based on a sequence of linear complementarity problems applied to a Walrasian equilibrium model: An example. Mathematical Programming 37(1987)1–18. · Zbl 0613.90098 · doi:10.1007/BF02591680
[41] R.D.C. Monteiro, J.S. Pang and T. Wang, A positive algorithm for the nonlinear complementarity problem, SIAM Journal on Optimization (1995). · Zbl 0832.90107
[42] J.J. Moré and S.J. Wright,Optimization Software Guide, No. 14 inFrontiers in Applied Mathematics, SIAM, Philadelphia, 1993. · Zbl 0830.65050
[43] B.A. Murtagh and M.A. Saunders, MINOS 5.0 user’s guide, Technical Report SOL 83-20, Department of Operations Research, Stanford University, CA, 1983.
[44] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, 1970. · Zbl 0241.65046
[45] J.S. Pang, A B-differentiable equation based, glovbally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Mathematical Programming 51(1991)101–132. · Zbl 0733.90063 · doi:10.1007/BF01586928
[46] J.S. Pang and S.A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem, Mathematical Programming 60(1993)295–338. · Zbl 0808.90123 · doi:10.1007/BF01580617
[47] C. Perroni and T. Rutherford, International trade in carbon emission rights and basic materials: General equilibrium calculations for 2020, Scandinavian Journal of Economics (1993).
[48] L. Qi and X. Chen, A globally convergent successive approximation method for nonsmooth equations, Technical Report, School of Mathematics, University of New South Wales, Sydney, 1993. · Zbl 0833.90109
[49] D. Ralph, Global convergence of damped Newton’s method for nonsmooth equations, via the path search, Mathematics of Operations Research 19(1994)352–389. · Zbl 0819.90102 · doi:10.1287/moor.19.2.352
[50] J.K. Reid, A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases. Mathematical Programming 24(1982)55–69. · Zbl 0492.90050 · doi:10.1007/BF01585094
[51] S.M. Robinson, Normal maps induced by linear transformations, Mathematics of Operations Research 17(1992)691–714. · Zbl 0777.90063 · doi:10.1287/moor.17.3.691
[52] S.M. Robinson, Newton’s method for a class of nonsmooth functions, Set Valued Analysis 2(1994) 291–305. · Zbl 0804.65062 · doi:10.1007/BF01027107
[53] T.F. Rutherford, MILES: A mixed inequality and nonlinear equation solver, Working Paper, Department of Economics, University of Colorado, Boulder, CA, 1993.
[54] T.F. Rutherford, Applied general equilibrium modeling with MPSGE as a GAMS subsystem, Manuscript, Department of Economics, University of Colorado, Boulder, CO, 1994. · Zbl 0951.91037
[55] T.F. Rutherford, Extensions of GAMS for complementarity problems arising in applied economic analysis, Journal of Economic Dynamics and Control (1995). · Zbl 0877.90074
[56] M. V. Solodov and P. Tseng, Modified projection-type methods for monotone variational inequalities, Mathematical Programming Technical report 94-04, Computer Sciences Department, University of Wisconsin, Madison, WI, 1994, Available from ftp: //ftp.cs.wisc.edu/math-prog/tech-reports/
[57] H. Torma and T. Rutherford, A general equilibrium assessment of Finland’s grand tax reform, Working Paper 15/1992, Department of Economics and Management, University of Jyväskylä, Finland, 1992.
[58] P. Tseng, N. Yamashita and M. Fukushima, Equivalence of complementarity problems to differentiable minimization: A unified approach, SIAM Journal on Optimization (1994). · Zbl 0853.65067
[59] S.J. Wright and D. Ralph, A superlinear infeasible-interior-point algorithm for monotone complementarity problems, Technical Report MCS-P344-1292, Argonne National Laboratory, Argonne, IL, 1993. · Zbl 0867.90112
[60] B. Xiao and P.T. Harker, A nonsmooth Newton method for variational inequalities I: Theory, Mathematical Programming 65(1994)151–194. · Zbl 0812.65048 · doi:10.1007/BF01581695
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.