Zonotopes and the LP-Newton method

摘要

Although linear programming problems can be solved in polynomial time by the ellipsoid method and interior-point algorithms, there still remains a longstanding open problem of devising a strongly polynomial algorithm for linear programming (or of disproving the existence of such an algorithm). The present work is motivated by an attempt toward solving this problem.rnLinear programming problems can be formulated in terms of a zonotope, a kind of greedy polyhedron, on which linear optimization is made easily. We propose a method, called the LP-Newton method, for linear programming that is based on the zonotope formulation and the minimum-norm-point algorithm of Philip Wolfe. The LP-Newton method is a finite algorithm even for real-number input data with exact arithmetic computations. We show some preliminary computational results to examine the behavior of the LP-Newton method.