A simplicial homotopy algorithm for computing zero points on polytopes

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 polytopeP. The proposed algorithm generates a piecewise linear path inP × [1, ) from any chosen interior pointx⁰ ofP 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 triangulation. The starting pointx⁰ is left in a direction to one vertex ofP. The direction in whichx⁰ leaves depends on the function value atx⁰ and the polytopeP. 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.