Solving discrete systems of nonlinear equations

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

Research output: Contribution to journalArticleScientificpeer-review

225 Downloads (Pure)

Abstract

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 Rn. 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 triangulation 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 obtain a discrete analogue of the well-known Borsuk–Ulam theorem and a theorem for the existence of a solution for the discrete nonlinear complementarity problem.
Original languageEnglish
Pages (from-to)493-500
JournalEuropean Journal of Operational Research
Volume214
Issue number3
Publication statusPublished - 2011

Fingerprint

Zero Point
System of Nonlinear Equations
Discrete Systems
Nonlinear equations
Triangulation
Piecewise Linear Approximation
n-dimensional
Oligopoly
Nonlinear Complementarity Problem
Terminate
Theorem
Convex Hull
Regular hexahedron
Boundary conditions
Existence Results
Fixed point theorem
Euclidean space
Finite Set
Analogue
Iteration

Cite this

van der Laan, G. ; Talman, A.J.J. ; Yang, Z.F. / Solving discrete systems of nonlinear equations. In: European Journal of Operational Research. 2011 ; Vol. 214, No. 3. pp. 493-500.
@article{81f0a46c3c9d4757bfa101c4a5b60fdf,
title = "Solving discrete systems of nonlinear equations",
abstract = "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 Rn. 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 triangulation 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 asimplicial 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 obtain a discrete analogue of the well-known Borsuk–Ulam theorem and a theorem for the existence of a solution for the discrete nonlinear complementarity problem.",
author = "{van der Laan}, G. and A.J.J. Talman and Z.F. Yang",
note = "Appeared earlier as CentER Discussion Paper 2008-105",
year = "2011",
language = "English",
volume = "214",
pages = "493--500",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science BV",
number = "3",

}

van der Laan, G, Talman, AJJ & Yang, ZF 2011, 'Solving discrete systems of nonlinear equations', European Journal of Operational Research, vol. 214, no. 3, pp. 493-500.

Solving discrete systems of nonlinear equations. / van der Laan, G.; Talman, A.J.J.; Yang, Z.F.

In: European Journal of Operational Research, Vol. 214, No. 3, 2011, p. 493-500.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Solving discrete systems of nonlinear equations

AU - van der Laan, G.

AU - Talman, A.J.J.

AU - Yang, Z.F.

N1 - Appeared earlier as CentER Discussion Paper 2008-105

PY - 2011

Y1 - 2011

N2 - 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 Rn. 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 triangulation 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 asimplicial 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 obtain a discrete analogue of the well-known Borsuk–Ulam theorem and a theorem for the existence of a solution for the discrete nonlinear complementarity problem.

AB - 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 Rn. 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 triangulation 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 asimplicial 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 obtain a discrete analogue of the well-known Borsuk–Ulam theorem and a theorem for the existence of a solution for the discrete nonlinear complementarity problem.

M3 - Article

VL - 214

SP - 493

EP - 500

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -