Topological structure and a polynomial-time solution of linear programming over the real numbers. (arXiv:1805.06342v1 [math.OC])

We present an O(mn^2) algorithm for linear programming over the real numbers with n variables and m problem constraints through deciding the support set a of the optimal solution. Let z and e be two 2(n+m)-tuples with z representing the prime, dual and slack variables of linear programming, and e the all-one vector. Let Z denote the region including all (tz, t) with z meeting the prime and dual problem constraints, the zero duality gap constraint, but not the non-negativity constraints, and no limit on the real number t. Let L be the projection of Z on the hyperplane defined by t = 0. Let Y denote the (n+m)-subspace where the sum of two components of a point corresponding to a complementary pair of z equals one, and Q be the sphere in Y centered at e/2 of a diameter whose square equals 2(n+m). Consider a squeeze mapping involving the variables of each complementary pair of z. The projection of e on the image of L of the mapping lies in Q, which is the circumsphere of the hypercube in Y查看全文

Solidot 文章翻译