Computing integral solutions of complementarity problems

In this paper an algorithm is proposed to find an integral solution of (nonlinear) complementarity problems. The algorithm starts with a nonnegative integral point and generates a unique sequence of adjacent integral simplices of varying dimension. Conditions are stated under which the algorithm terminates with a simplex, one of whose vertices is an integral solution of the complementarity problem under consideration.     

A new simplicial variable dimension algorithm to find equilibria on the product space of unit simplices

A new simplicial variable dimension restart algorithm is introduced to solve the nonlinear complementarity problem on the product spaceS of unit simplices. The triangulation which underlies the algorithm differs from the triangulations ofS used thus far. Moreover, the number of rays along which the algorithm can leave the arbitrarily chosen starting point is much larger. More precisely, there is a ray leading from the starting point to each vertex ofS. In caseS is the product ofn one-dimensional unit simplices the alogrithm is similar to the octahedral algorithm onR ⁿ having 2 ⁿ rays. Also, the accuracy of an approximate solution in the terminal simplex of the algorithm is in general better than for the other algorithms onS. Computational results will show that the number of iterations for the new algorithm is much less. The examples concern the computation of equilibria in noncooperative games, exchange economies and trade models. This author is financially supported by the Netherlands Organisation for the Advancement of Pure Research (ZWO), Grant 46-98. This research is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply” which has been approved by the Netherlands ministry of education and sciences.     

A variable dimension fixed point algorithm and the orientation of simplices

A variable dimension algorithm with integer labelling is proposed for solving systems ofn equations inn variables. The algorithm is an integer labelling version of the 2-ray algorithm proposed by the author. The orientation of lower dimensional simplices is studied and is shown to be preserved along a sequence of adjacent simplices.     

Computing an Integer Point of a Class of Convex Sets

A simplicial algorithm is proposed for computing an integer point of a convex set ^CRn satisfying

Weighted projective spaces and reflexive simplices

 We derive a classification algorithm for reflexive simplices in arbitrary fixed dimension. It is based on the assignment of a weight Q ? ℕ ⁿ⁺¹ to an integral n-simplex, the construction, up to an isomorphism, of all simplices with given weight Q, and the characterization in terms of the weight as to when a simplex with reduced weight is reflexive. This also yields a convex-geometric reproof of the characterization in terms of weights for weighted projective spaces to have at most Gorenstein singularities. Received: 30 March 1999 / Revised version: 18 October 2001     

Largest integral simplices with one interior integral point: Solution of Hensley's conjecture and related results

For each dimension d, d-dimensional integral simplices with exactly one interior integral point have bounded volume. This was first shown by Hensley. Explicit volume bounds were determined by Hensley, Lagarias and Ziegler, Pikhurko, and Averkov. In this paper we determine the exact upper volume bound for such simplices and characterize the volume-maximizing simplices. We also determine the sharp upper bound on the coefficient of asymmetry of an integral polytope with a single interior integral point. This result confirms a conjecture of Hensley from 1983. Moreover, for an integral simplex with precisely one interior integral point, we give bounds on the volumes of its faces, the barycentric coordinates of the interior integral point and its number of integral points. Furthermore, we prove a bound on the lattice diameter of integral polytopes with a fixed number of interior integral points. The presented results have applications in toric geometry and in integer optimization.     

Orthocentric simplices and their centers

A simplex is said to be orthocentric if its altitudes intersect in a common point, called its orthocenter. In this paper it is proved that if any two of the traditional centers of an orthocentric simplex (in any dimension) coincide, then the simplex is regular. Along the way orthocentric simplices in which all facets have the same circumradius are characterized, and the possible barycentric coordinates of the orthocenter are described precisely. In particular these barycentric coordinates are used to parametrize the shapes of orthocentric simplices. The substantial, but widespread, literature on orthocentric simplices is briefly surveyed in order to place the new results in their proper context, and some of the previously known results are given with new proofs from the present perspective.     

A class of simplicial restart fixed point algorithms without an extra dimension

In an earlier paper we introduced an algorithm for approximating a fixed point of a mapping on the product space of unit simplices. Ideas of that paper are used to construct a class of triangulations ofR ⁿ. More precisely, for somek, 1 k n, and positive integersm ₁ , m_k with sumn, a triangulation ofR ⁿ is obtained by triangulating the cells which are formed by taking the product of given triangulations ofR ^mj, j = 1, ,k. The triangulation of each cell will be defined in relation to an arbitrarily chosen pointv inR ⁿ, being the starting point of the algorithm. Fork = n we obtain theK triangulation originally due to Todd. Each element of the class can be used to find a simplex which approximates a fixed point of a mapping onR ⁿ by generating a unique path of adjacent simplices of variable dimension starting with the pointv. We also give convergence conditions. It is indicated how in casek = n a connected set of fixed points can be generated. Moreover, we give some computational experience.     

Cutting hyperplanes for divide-and-conquer

Givenn hyperplanes inE ^d, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together coverE ^d and such that the interior of each simplex intersects at mostn/r hyperplanes. We present a deterministic algorithm for computing a (1/r)-cutting ofO(r ^d) size inO(nr ^d–1) time. If we require the incidences between the hyperplanes and the simplices of the cutting to be provided, then the algorithm is optimal. Our method is based on a hierarchical construction of cuttings, which also provides a simple optimal data structure for locating a point in an arrangement of hyperplanes. We mention several other applications of our result, e.g., counting segment intersections, Hopcroft's line/point incidence problem, linear programming in fixed dimension.This research was supported in part by the National Science Foundation under Grant CCR-9002352.     

The (2 n+1−2)-ray algorithm: A new simplicial algorithm to compute economic equilibria

A new variable dimension simplicial restart algorithm is introduced to compute economic equilibria. The number of rays along which the algorithm can leave the starting point differs from the thusfar known algorithms. More precisely, the new algorithm has one ray to each of the 2 ⁿ⁺¹−2 faces of then-dimensional price simplex, whereas the existing algorithms haven+1 rays either to each facet or to each vertex of the unit simplex. The path of points followed by the algorithm can be interpreted as a globally and universally convergent price adjustment process. The process is also economically meaningful and therefore it is a good alternative for the well-known Walras' tatonnement process. Computational results show that the algorithm is competitive with the most efficient simplicial algorithms developed thusfar. This work is part of theVF-program “Equilibrium and Disequilibrium in Demand and Supply”, which has been approved by the Netherlands Ministry of Education and Sciences.     

The Angle Defect for Odd-Dimensional Simplicial Manifolds

In a 1967 paper, Banchoff stated that a certain type of polyhedral curvature, that applies to all finite polyhedra, was zero at all vertices of an odd-dimensional polyhedral manifold; one then obtains an elementary proof that odd-dimensional manifolds have zero Euler characteristic. In a previous paper, the author defined a different approach to curvature for arbitrary simplicial complexes, based upon a direct generalization of the angle defect. The generalized angle defect is not zero at the simplices of every odd-dimensional manifold. In this paper we use a sequence based upon the Bernoulli numbers to define a variant of the angle defect for finite simplicial complexes that still satisfies a Gauss-Bonnet-type theorem, but is also zero at any simplex of an odd-dimensional simplicial complex K (of dimension at least 3), such that χ(link(ηⁱ, K)) = 2 for all i-simplices ηⁱ of K, where i is an even integer such that 0 ≤ i ≤ n – 1. As a corollary, an elementary proof is given that any such simplicial complex has Euler characteristic zero.     

双曲空间中Veljan-Korchmaros型不等式及应用

本文研究了双曲空间Hn(K)中n维高维单形的几何不等式问题.利用距离几何的理论与方法,获得了涉及n维双曲单形体积,侧面积与棱长的几个几何不等式,这些几何不等式是双曲单形几何不等式的基础.     

Parametric methods in integer linear programming

In contrast to methods of parametric linear programming which were developed soon after the invention of the simplex algorithm and are easily included as an extension of that method, techniques for parametric analysis on integer programs are not well known and require considerable effort to append them to an integer programming solution algorithm.The paper reviews some of the theory employed in parametric integer programming, then discusses algorithmic work in this area over the last 15 years when integer programs are solved by different methods. A summary of applications is included and the article concludes that parametric integer programming is a valuable tool of analysis awaiting further popularization.     

A Circumradius-Inradius Identity and an Identity Relating Volumes for a Simplex

We establish an identity for an n-dimensional simplex relating the circumradius and the inradius, and an identity relating its volume and the pedal volume. As applications, we derive some known inequalities for simplices and generalizations of such inequalities.     

A simplicial approximation of a solution for the nonlinear complementarity problem

For a given map f from the n-dimensional Euclidean space En into itself, we consider the complementary problem of finding a nonnegative vector x in En whose imagef(x) is also nonnegative and such that the two vectors are orthogonal. It is the unifying mathematical form for several problems arising in different fields such as mathematical programming, game theory and economics.In this paper a new algorithm is developed based on the adjacent simplex technique , which was used by Garcia, Lemke and Lüthi for approximating an equilibrium point of a noncooperative n-person game. An almost-complementary path leads to a complementary simplex, which approximates a stationary point. Because most of the existence proofs for the nonlinear complementarity use the relationship between stationary points and complementarity, the algorithm gives constructive proofs for many existence theorems. If a better approximation is desired, the algorithm may be restarted from any point. The dimension of the simplices on the path is varying, which computationally should result in some savings.     

Volume and Lattice Points of Reflexive Simplices

Using new number-theoretic bounds on the denominators of unit fractions summing up to one, we show that in any dimension d ≥ 4 there is only one d-dimensional reflexive simplex having maximal volume. Moreover, only these reflexive simplices can admit an edge that has the maximal number of lattice points possible for an edge of a reflexive simplex. In general, these simplices are also expected to contain the largest number of lattice points even among all lattice polytopes with only one interior lattice point. Translated in algebro-geometric language, our main theorem yields a sharp upper bound on the anticanonical degree of d-dimensional Q-factorial Gorenstein toric Fano varieties with Picard number one, e.g., of weighted projective spaces with Gorenstein singularities.     

Low dimensional simplex evolution: a new heuristic for global optimization

This paper presents a new heuristic for global optimization named low dimensional simplex evolution (LDSE). It is a hybrid evolutionary algorithm. It generates new individuals following the Nelder-Mead algorithm and the individuals survive by the rule of natural selection. However, the simplices therein are real-time constructed and low dimensional. The simplex operators are applied selectively and conditionally. Every individual is updated in a framework of try-try-test. The proposed algorithm is very easy to use. Its efficiency has been studied with an extensive testbed of 50 test problems from the reference (J Glob Optim 31:635–672, 2005). Numerical results show that LDSE outperforms an improved version of differential evolution (DE) considerably with respect to the convergence speed and reliability.     

Solving discrete systems of nonlinear equations

We study the existence problem of a zero point of a function defined on a finite set of elements of the integer lattice Zⁿ of the n-dimensional Euclidean space Rⁿ. 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 Zⁿ 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.     

Canonical Dimension Of Orthogonal Groups

We prove Berhuy-Reichstein's conjecture on the canonical dimension of orthogonal groups showing that for any integer n ≥ 1, the canonical dimension of SO_2n+1 and of SO_2n+2 is equal to n(n + 1)/2. More precisely, for a given (2n + 1)-dimensional quadratic form φ defined over an arbitrary field F of characteristic ≠ 2, we establish a certain property of the correspondences on the orthogonal grassmannian X of n-dimensional totally isotropic subspaces of φ, provided that the degree over F of any finite splitting field of φ is divisible by 2ⁿ; this property allows us to prove that the function field of X has the minimal transcendence degree among all generic splitting fields of φ.