This paper presents a new polynomial-time algorithm for linear programming, which has a running time of O(n³·⁵L²), significantly faster than the ellipsoid algorithm's O(n⁶L²). The algorithm uses projective transformations to map a polytope and an interior point into a new space where the ratio of the radius of the smallest sphere containing the polytope to the radius of the largest sphere contained within it is O(n). This allows for efficient optimization over an inscribed sphere, leading to a sequence of points that converge to the optimal solution in polynomial time.
The algorithm is based on repeated projective transformations followed by optimization over an inscribed sphere. It is shown that any strictly interior point in the feasible region can be mapped to any other such point via a transformation that preserves affine spaces and metric properties. This transformation is independent of the objective function and allows for efficient computation.
The algorithm's complexity is analyzed, showing that the factor L in the running time comes from the number of steps and the precision required for arithmetic operations. The algorithm can find an approximate solution with a fixed fraction of the optimal value in O(n) steps, saving a factor of L. The complexity of finding an exact solution is expressed in terms of a "discreteness factor" R, which is the ratio of the difference between the best and worst objective function values to the difference between the best and next best values.
The algorithm is also shown to be numerically stable, with round-off errors not accumulating but being self-correcting. It can handle multiple columns and is suitable for parallel computation. The algorithm's performance is evaluated in practice, showing that it can efficiently solve linear programming problems by optimizing over an ellipsoid or solving a linear system of equations.
The algorithm is described in detail, including its steps, the use of projective transformations, and the optimization of the objective function over an inscribed sphere. Theoretical analysis shows that the algorithm converges to the optimal solution in polynomial time, with the potential function being invariant under projective transformations. The algorithm's complexity is O(n³·⁵L²), making it significantly faster than the ellipsoid algorithm.This paper presents a new polynomial-time algorithm for linear programming, which has a running time of O(n³·⁵L²), significantly faster than the ellipsoid algorithm's O(n⁶L²). The algorithm uses projective transformations to map a polytope and an interior point into a new space where the ratio of the radius of the smallest sphere containing the polytope to the radius of the largest sphere contained within it is O(n). This allows for efficient optimization over an inscribed sphere, leading to a sequence of points that converge to the optimal solution in polynomial time.
The algorithm is based on repeated projective transformations followed by optimization over an inscribed sphere. It is shown that any strictly interior point in the feasible region can be mapped to any other such point via a transformation that preserves affine spaces and metric properties. This transformation is independent of the objective function and allows for efficient computation.
The algorithm's complexity is analyzed, showing that the factor L in the running time comes from the number of steps and the precision required for arithmetic operations. The algorithm can find an approximate solution with a fixed fraction of the optimal value in O(n) steps, saving a factor of L. The complexity of finding an exact solution is expressed in terms of a "discreteness factor" R, which is the ratio of the difference between the best and worst objective function values to the difference between the best and next best values.
The algorithm is also shown to be numerically stable, with round-off errors not accumulating but being self-correcting. It can handle multiple columns and is suitable for parallel computation. The algorithm's performance is evaluated in practice, showing that it can efficiently solve linear programming problems by optimizing over an ellipsoid or solving a linear system of equations.
The algorithm is described in detail, including its steps, the use of projective transformations, and the optimization of the objective function over an inscribed sphere. Theoretical analysis shows that the algorithm converges to the optimal solution in polynomial time, with the potential function being invariant under projective transformations. The algorithm's complexity is O(n³·⁵L²), making it significantly faster than the ellipsoid algorithm.