Research Initiation Award: Polar Geometric Approach to Linear Programming

9308953普拉布这项研究将探索线性规划(LP)的一种新方法。该方法利用了凸多面体理论和极性理论的基本结果，这些结果以前没有被应用于线性规划计算。初步研究表明，该方法具有产生比当前LP算法更快的高效算法的前景。该工作描述了基于该方法设计高效线性规划算法的两种方法：Gale变换法和单纯求精法。这些方法应用了关于多面体的组合和度量结构的经典结果，以使计算高效。这些方法的计算实验将与理论研究并行进行，以确保所产生的算法在理论上是有效的。在过去，人们花费了大量的理论和计算研究工作，试图将边缘跟随单纯形法转换为最坏情况下的多项式时间算法。广义SIMPLE方案可能意义重大，因为它为寻求最坏情况下的多项式时间单纯形算法提供了一种新的方法。如果实现了这些目标，结果将对解决现实世界的问题产生重大影响。

9308953 Prabhu The research will investigate a new approach to Linear Programming (LP). The approach exploits fundamental results from Convex Polytope Theory and Polarity Theory that have not been applied to LP computation previously. Preliminary studies suggest that the approach has prospects of yielding an efficient algorithm that could be faster than the current LP algorithms. The work describes two methods for devising an efficient LP algorithm based on the suggested approach: Gale Transform Method and Simplicial Refinement Method. The methods apply classic results on the combinatorial and metric structure of polytopes to make computation efficient. Computational experiments on the methods will be undertaken in parallel with theoretical investigations in order to ensure that the resulting algorithm will be theoretically efficient. Enormous theoretical and computational research effort has been expended in the past on attempts to convert the edge-following Simplex method into a worst-case polynomial-time algorithm . The Generalized Simple scheme can be significant, in that it proffers a fresh approach to the quest for worst-case polynomial-time Simplex algorithms. If these goals are achieved, the results will have significant impact in solving real world problems.