数学物理学报(英文版) ›› 1991, Vol. 11 ›› Issue (1): 111-120.

• 论文 • 上一篇    

HOMOTOPY SIMPLEX PIVOT ALGORITHM

徐森林1, 刘书麟2   

  1. 1. University of Science and Technology of China, Hefei, China;
    2. Institute of Systoms Science, Academic Sinica, Beijing, China
  • 收稿日期:1985-06-18 修回日期:1989-06-02 出版日期:1991-03-25 发布日期:1991-03-25

HOMOTOPY SIMPLEX PIVOT ALGORITHM

Xu Senlin1, Liu Shulin2   

  1. 1. University of Science and Technology of China, Hefei, China;
    2. Institute of Systoms Science, Academic Sinica, Beijing, China
  • Received:1985-06-18 Revised:1989-06-02 Online:1991-03-25 Published:1991-03-25

摘要: In this paper, we study the properties of the zero set of a homotopy H:Im×[0, 1]→ Rm and its piecewise linear approximation φδi:Im×[0, 1]→Rm, These properties are very important for the homotopy simplex pivot algorithm. However, we prove that for almost every polynomial mapping the zero set of linear homotopy H(z, t)=tp(z)+(1-t)Q(z) consists of q=∏j=1nqj disjoint differential curves, and the zero set of its piecewise linear approximation φδi, consists of some broken lines. Where δi→0, these broken lines tend to differential curves in the zero set of H.

Abstract: In this paper, we study the properties of the zero set of a homotopy H:Im×[0, 1]→ Rm and its piecewise linear approximation φδi:Im×[0, 1]→Rm, These properties are very important for the homotopy simplex pivot algorithm. However, we prove that for almost every polynomial mapping the zero set of linear homotopy H(z, t)=tp(z)+(1-t)Q(z) consists of q=∏j=1nqj disjoint differential curves, and the zero set of its piecewise linear approximation φδi, consists of some broken lines. Where δi→0, these broken lines tend to differential curves in the zero set of H.