A mapping f ： Z^n → Rn is said to possess the direction preserving property if fi（x） 〉 0 implies fi（y） ≥ 0 for any integer points x and y with ｜｜x - y｜｜∞≤ 1. In this paper, a simplicial algorithm is deve...A mapping f ： Z^n → Rn is said to possess the direction preserving property if fi（x） 〉 0 implies fi（y） ≥ 0 for any integer points x and y with ｜｜x - y｜｜∞≤ 1. In this paper, a simplicial algorithm is developed for computing an integer zero point of a mapping with the direction preserving property. We assume that there is an integer point x^0 with c ≤ x^0≤d satisfying that maxl≤i≤（xi - xi^0）fi（x） 〉 0 for any integer point x with f（x） ≠ 0 on the boundary of H = {x ∈R^n [c-e ≤ x〈d＋e},wherecanddaretwo finite integer points with c 〈 d and e = （1, 1,... , 1）^T E R^n. This assumption is implied by one of two conditions for the existence of an integer zero point of a mapping with the preserving property in van der Laan et al. （2004）. Under this assumption, starting at x^0, the algorithm follows a finite simplicial path and terminates at an integer zero point of the mapping. This result has applications in general economic equilibrium models with indivisible commodities.展开更多
In this paper a triangulation of continuous and arbitrary refinement of grid sizes is proposed for simplicial homotopy algorithms to compute zero points on a polytope P. The proposed algorithm generates a piecewise li...In this paper a triangulation of continuous and arbitrary refinement of grid sizes is proposed for simplicial homotopy algorithms to compute zero points on a polytope P. The proposed algorithm generates a piecewise linear path in P × [1,∞) from any chosen interior point x0 of P on level {1} to a solution of the underlying problem. The path is followed by making linear programming pivot steps in a linear system and replacement steps in the triangnlation.The starting point x0 is left in a direction to one vertex of P. The direction in which x0 leaves depends on the function value at x0 and the polytope P. Moreover, we also give a new equivalent form of the Brouwer fixed point theorem on polytopes. This form has many important applications in mathematical programming and the theory of differential equations.展开更多
文摘A mapping f ： Z^n → Rn is said to possess the direction preserving property if fi（x） 〉 0 implies fi（y） ≥ 0 for any integer points x and y with ｜｜x - y｜｜∞≤ 1. In this paper, a simplicial algorithm is developed for computing an integer zero point of a mapping with the direction preserving property. We assume that there is an integer point x^0 with c ≤ x^0≤d satisfying that maxl≤i≤（xi - xi^0）fi（x） 〉 0 for any integer point x with f（x） ≠ 0 on the boundary of H = {x ∈R^n [c-e ≤ x〈d＋e},wherecanddaretwo finite integer points with c 〈 d and e = （1, 1,... , 1）^T E R^n. This assumption is implied by one of two conditions for the existence of an integer zero point of a mapping with the preserving property in van der Laan et al. （2004）. Under this assumption, starting at x^0, the algorithm follows a finite simplicial path and terminates at an integer zero point of the mapping. This result has applications in general economic equilibrium models with indivisible commodities.
文摘In this paper a triangulation of continuous and arbitrary refinement of grid sizes is proposed for simplicial homotopy algorithms to compute zero points on a polytope P. The proposed algorithm generates a piecewise linear path in P × [1,∞) from any chosen interior point x0 of P on level {1} to a solution of the underlying problem. The path is followed by making linear programming pivot steps in a linear system and replacement steps in the triangnlation.The starting point x0 is left in a direction to one vertex of P. The direction in which x0 leaves depends on the function value at x0 and the polytope P. Moreover, we also give a new equivalent form of the Brouwer fixed point theorem on polytopes. This form has many important applications in mathematical programming and the theory of differential equations.
