论文研究 线性规划的滑动梯度算法

数十年来，人们一直在寻求用于线性规划（LP）的强多项式算法。 最近，出现了一种称为重力滑动算法[1]的新方法。 这是一种梯度下降方法，该下降轨迹沿多面体的内表面滑动，直到到达最佳点为止。 在R3中，重力吸引的水滴沿着最短的路径下降到最低点。 由于重力滑动算法模拟了水滴的轨迹，因此在R3中表现出很强的多项式行为。 我们认为，对于Rn中的线性规划，它也可能是一个强多项式算法。 实际上，我们的算法仅需两次迭代即可解决Klee-Minty变形立方体问题，而与立方体的尺寸无关。 重力滑动算法的核心是如何计算重力矢量g在一组小平面的交点上的投影，这在同一篇论文中已公开[1]。 在本文中，我们引入了一种更有