A Technique for Bounding the Number of Iterations in Path Following Algorithms
A Technique for Bounding the Number of Iterations in Path Following Algorithms
复制标题
DOI：
10.1142/9789814354363_0021
复制
发表时间：
1993-07
期刊：
影响因子：
--
通讯作者：
P. M. Vaidya;David S. Atkinson
中科院分区：
文献类型：
--
作者：
P. M. Vaidya;David S. Atkinson
我们提出了一种技术，通过基于正定 Hessian 凸障碍函数大小的两种度量的组合来限制路径跟踪线性规划算法中所需的迭代次数。我们还提出了一种新的屏障函数，它是先前研究的两种屏障函数的混合体。我们限制迭代次数的技术表明，混合结果的迭代次数比其任何一个组件都要少。
We present a technique that bounds the number of iterations required in a path following linear programming algorithm via a combination of two measures based on the size ofwhereis a convex barrier function with positive definite Hessian. We also present a new barrier function that is a hybrid of two previously studied barrier functions. Our technique for bounding the number of iterations shows that the hybrid results in a smaller number of iterations than does either of its components.