Solving Discrete Systems of Nonlinear Equations

G. van der Laan, A.J.J. Talman, Z.F. Yang

Research output: Working paperDiscussion paperOther research output

223 Downloads (Pure)

Abstract

In this paper we study the existence problem of a zero point of a function defined on a finite set of elements of the integer lattice Zn of the n-dimensional Euclidean space IRn. It is assumed that the set is integrally convex, which implies that the convex hull of the set can be subdivided in simplices such that every vertex is an element of Zn and each simplex of the triangulation lies in an n-dimensional cube of size one. With respect to this triangu- lation we assume that the function satisfies some property that replaces continuity. Under this property and some boundary condition the function has a zero point. To prove this we use a simplicial algorithm that terminates with a zero point within a finite number of iterations. The standard technique of applying a fixed point theorem to a piecewise linear approximation cannot be applied, because the `continuity property' is too weak to assure that a zero point of the piecewise linear approximation induces a zero point of the function itself. We apply the main existence result to prove the existence of a pure Cournot-Nash equilibrium in a Cournot oligopoly model. We further adapt the main result to a discrete variant of the well-known Borsuk-Ulam theorem and to a theorem for the existence of a solution for the discrete nonlinear complementarity problem.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages22
Volume2008-105
Publication statusPublished - 2008

Publication series

NameCentER Discussion Paper
Volume2008-105

Keywords

  • integrally convex set
  • triangulation
  • simplicial algorithm
  • discrete zero point

Fingerprint Dive into the research topics of 'Solving Discrete Systems of Nonlinear Equations'. Together they form a unique fingerprint.

  • Cite this

    van der Laan, G., Talman, A. J. J., & Yang, Z. F. (2008). Solving Discrete Systems of Nonlinear Equations. (CentER Discussion Paper; Vol. 2008-105). Operations research.