The Sliding Gradient Algorithm for Linear Programming

• 作者: Hochung Liu Peizhuang Wang
• 来源期刊: 美国运筹学期刊(英文)
• 学科: 数学
• 关键词: LINEAR PROGRAMMING MATHEMATICAL PROGRAMMING COMPLEXITY THEORY Optimization
• 年，卷（期）: 2018,（2）
• 页码范围: 112-131
• 页数: 20页
• 分类号: O1

摘要

The existence of strongly polynomial algorithm for linear programming (LP) has been widely sought after for decades. Recently, a new approach called Gravity Sliding algorithm [1] has emerged. It is a gradient descending method whereby the descending trajectory slides along the inner surfaces of a polyhedron until it reaches the optimal point. In R3, a water droplet pulled by gravitational force traces the shortest path to descend to the lowest point. As the Gravity Sliding algorithm emulates the water droplet trajectory, it exhibits strongly polynomial behavior in R3. We believe that it could be a strongly polynomial algorithm for linear programming in Rn too. In fact, our algorithm can solve the Klee-Minty deformed cube problem in only two iterations, irrespective of the dimension of the cube. The core of gravity sliding algorithm is how to calculate the projection of the gravity vector g onto the intersection of a group of facets, which is disclosed in the same paper [1]. In this paper, we introduce a more efficient method to compute the gradient projections on complementary facets, and rename it the Sliding Gradient algorithm under the new projection calculation.