Author(s)

Hochung Liu, Peizhuang Wang

College of Intelligence Engineering and Mathematics, Liaoning Technical University, Fuxin, China.

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 R³, 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 R³. We believe that it could be a strongly polynomial algorithm for linear programming in Rⁿ 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.

Linear Programming, Mathematical Programming, Complexity Theory, Optimization

Liu, H. and Wang, P. (2018) The Sliding Gradient Algorithm for Linear Programming. American Journal of Operations Research, 8, 112-131. doi: 10.4236/ajor.2018.82009.