A simplicial homotopy algorithm for computing zero points on polytopes |
| |
Authors: | Kaizhou Chen Zaifu Yang Zhengli Liang |
| |
Affiliation: | (1) Department of Applied Mathematics, Xidian University, 710071 Xi'an, China |
| |
Abstract: | 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 pointx0 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 pointx0 is left in a direction to one vertex ofP. The direction in whichx0 leaves depends on the function value atx0 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. |
| |
Keywords: | Zero point simplicial homotopy algorithm variable dimension algorithm triangulation polytope. |
本文献已被 CNKI SpringerLink 等数据库收录! |