×

zbMATH — the first resource for mathematics

An algorithm based on a sequence of linear complementarity problems applied to a Walrasian equilibrium model: An example. (English) Zbl 0613.90098
The Walrasian equilibrium problem is cast as a complementarity problem, and its solution is computed by solving a sequence of linear complementarity problems (SLCP). Earlier numerical experiments have demonstrated the computational efficiency of this approach. So far, however, there exist few relevant theoretical results that characterize the performance of this algorithm. In the context of a simple example of a Walrasian equilibrium model, we study the iterates of the SLCP algorithm. We show that a particular LCP of this process may have no, one or more complementary solutions. Other LCPs may have both homogeneous and complementary solutions. These features complicate the proof of convergence for the general case.
For this particular example, however, we are able to show that Lemke’s algorithm computes a solution to an LCP if one exists, and that the iterative process converges globally.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C90 Applications of mathematical programming
91B50 General equilibrium theory
65K05 Numerical mathematical programming methods
PDF BibTeX Cite
Full Text: DOI
References:
[1] R.W. Cottle and G.B. Dantzig, ”Complementary pivot theory of mathematical programming,”Linear Algebra and its Applications 1 (1968) 103–125. · Zbl 0155.28403
[2] B.C. Eaves, ”The linear complementarity problem,”Management Science 17 (1971) 612–634. · Zbl 0228.15004
[3] B.C. Eaves, ”A locally quadratically convergent algorithm for computing stationary points,” SOL Technical Report 78-13, Systems Optimization Laboratory, Department of Operations Research, Stanford University, (Stanford, CA, 1978). · Zbl 0458.65057
[4] N.H. Josephy, ”Newton’s method for generalized equations,” Technical Report (1965), Mathematics Research Center, University of Wisconsin (Madison, WI, 1979).
[5] T.J. Kehoe, ”Multiplicity of equilibria and comparative statics,”The Quarterly Journal of Economics (1985) 119–147. · Zbl 0581.90015
[6] C.E. Lemke, ”Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689. · Zbl 0139.13103
[7] L. Mathiesen, ”Computational experience in solving equilibrium models by a sequence of linear complementarity problems,”Operations Research 33, 6 (1985) 1225–1250. · Zbl 0583.90097
[8] L. Mathiesen, ”Computation of economic equilibria by a sequence of linear complementarity problems,”Mathematical Programming Study 23 (1985) 144–162. · Zbl 0579.90093
[9] L. Mathiesen and T. Rutherford, ”Testing the robustness of an iterative LCP algorithm for solving Walrasian equilibrium models,” Discussion Paper, 0883, Norwegian School of Economics and Business Administration, Bergen, 1983).
[10] J. S. Pang and D. Chan, ”Iterative methods for variational and complementarity problems,”Mathematical Programming 24 (1982) 284–313. · Zbl 0499.90074
[11] P.V. Preckel, ”Intertemporal equilibrium models: Development and results,” Ph.D. Dissertation, Department of Operations Research, Stanford University (Standford CA, 1983).
[12] P.V. Preckel,” Alternative algorithms for computing economic equilibria,”Mathematical Programming Study 23 (1985) 163–172. · Zbl 0574.90092
[13] S.M. Robinson, ”Strongly regular generalized equations,”Mathematics of Operations Research 5 (1980) 43–62. · Zbl 0437.90094
[14] H.E. Scarf, ”Some examples of global instability of the competitive equilibrium,”International Economic Review 1 3 (1960) 157–171. · Zbl 0096.14204
[15] H.E. Scarf with collaboration of T. Hansen,Computation of Economic Equilibria (Yale University Press, New Haven, CT, 1973).
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.