An algorithm for the linear complementarity problem with upper and lower bounds

In this paper, we adapt the octahedral simplicial algorithm for solving systems of nonlinear equations to solve the linear complementarity problem with upper and lower bounds. The proposed algorithm generates a piecewise linear path from an arbitrarily chosen pointz ⁰ to a solution point. This path is followed by linear programming pivot steps in a system ofn linear equations, wheren is the size of the problem. The starting pointz ⁰ is left in the direction of one of the 2 ⁿ vertices of the feasible region. The ray along whichz ⁰ is left depends on the sign pattern of the function value atz ⁰. The sign pattern of the linear function and the location of the points in comparison withz ⁰ completely govern the path of the algorithm.This research is part of the VF-Program Equilibrium and Disequilibrium in Demand and Supply, approved by the Netherlands Ministry of Education, Den Haag, The Netherlands.     

A new pivoting algorithm for the linear complementarity problem allowing for an arbitrary starting point

The linear complementarity problem is to find nonnegative vectors which are affinely related and complementary. In this paper we propose a new complementary pivoting algorithm for solving the linear complementarity problem as a more efficient alternative to the algorithms proposed by Lemke and by Talman and Van der Heyden. The algorithm can start at an arbitrary nonnegative vector and converges under the same conditions as Lemke's algorithm.This research is part of the VF-program Competition and Cooperation.     

Variational solution of the single-particle Dirac equation in the field of two nuclei using relativistically adapted Slater basis functions

A variational method for solving the time-independent single-particle Dirac equation in the Coulomb field of two nuclei is described. A minimax variational principle and basis functions that have the proper analytic behavior, i.e. behave like r ^γ,γ non-integer, in the neighborhood of a nucleus, are used. A momentum space integration scheme for computing the necessary two-center integrals is described. Results are given for a standard test problem on two nuclei with Z=90 with an internuclear separation of 2.0/Z. The results confirm those of a previous calculation [F.A. Parpia and A.K. Mohanty, Chem Phys Lett 238: 209 (1995)]. Received: 13 May 1998 / Accepted: 22 June 1998 / Published online: 28 August 1998     

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.     

A constructive proof of Ky Fan’s coincidence theorem

We present a constructive proof for the well-known Ky Fan’s coincidence theorem through a simplicial algorithm. In a finite number of steps the algorithm generates a simplex containing an approximate coincidence point. In the limit, when the mesh size converges to zero, the sequence of approximations converges to a coincidence point. This research was carried out while the second author was visiting the CentER for Economic Research, Tilburg University. He would like to thank both CentER and the Netherlands Organization for Scientific Research (NWO) for their financial support.     

Simplicial zero-point algorithms: A unifying description

In this paper, we consider the limiting paths of simplicial algorithms for finding a zero point. By rewriting the zero-point problem as a problem of finding a stationary point, the problem can be solved by generating a path of stationary points of the function restricted to an expanding convex, compact set. The limiting path of a simplicial algorithm to find a zero point is obtained by choosing this set in an appropriate way. Almost all simplicial algorithms fit in this framework. Using this framework, it can be shown very easily that Merrill's condition is sufficient for convergence of the algorithms.     

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.     

Volume flexibility and capacity investment: a real options approach

This paper considers the investment decision of a firm where it has to decide about the timing and capacity. We obtain that in a fast-growing market, right after investment the firm produces below capacity, where the utilization rate (the proportion of capacity that is used for production right after the investment) increases with market uncertainty for a very big market trend, and shows no monotonicity for a moderately large market trend. On the other hand, we get that, for a slowly growing or shrinking market, the firm produces up to capacity right after investment. In the intermediate case, the firm produces up to capacity right after investment when uncertainty is low and below capacity when uncertainty is high, whereas the utilization rate decreases with the market uncertainty.     

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.