A numerical LP-Newton method for solving linear programming using separating hyperplanes

We propose an LP-Newton-type method for linear programming (LP) with box constraints. In the standard LP-Newton method, each iteration computes a separating hyperplane using the Wolfe algorithm to find the minimum-norm point in a convex polytope. Because this inner routine can be computationally expensive in the worst case (and the Wolfe algorithm may require exponential time), we replace it with a simpler procedure that separates the origin from the convex hull of projected points. This change retains the Newton-type iterative framework while avoiding a potentially intractable inner routine, because the separating hyperplane can be constructed much more efficiently. We also derive an upper bound on the number of iterations. In our experiments, the resulting Naive Separation Algorithm (NSA) ran faster in some settings than the simplex method, which is often cited as one of the Top 10 Algorithms of the 20th Century ^[1]. These results suggest that this direction may lead to efficient algorithms for box-constrained LP.