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 [
Publications
- Article type
- Year
Article type
Year
Open Access
Research Article
Issue
AIMS Mathematics 2026, 11(2): 4691-4704
Published: 26 February 2026
Downloads:7
Total 1
京公网安备11010802044758号