Search Advanced

AIMS Mathematics

2026, Volume 11, Issue 2: 4691-4704. doi: 10.3934/math.2026191
Previous Article Next Article
Research article Topical Sections

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

  • Graduate School of Management, Tokyo University of Science, 1-11-2 Fujimi, Chiyoda-ku, Tokyo 102-0071, Japan
  • Published: 26 February 2026

  • MSC : 65K05, 90C05

  • 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.

    Citation: Yuki Matsuno. A numerical LP-Newton method for solving linear programming using separating hyperplanes[J]. AIMS Mathematics, 2026, 11(2): 4691-4704. doi: 10.3934/math.2026191

    Related Papers:

  • 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.



    加载中


    [1] J. Dongarra, F. Sullivan, Guest editors introduction to the top 10 algorithms, Comput. Sci. Eng., 2 (2000), 22–23. https://doi.org/10.1109/MCISE.2000.814652 doi: 10.1109/MCISE.2000.814652
    [2] G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, In: Activity analysis of production and allocation, New York: Wiley, 1951,339–347.
    [3] V. Klee, G. J. Minty, How good is the simplex algorithm?, In: Inequalities III, New York: Academic Press, 1972,159–175.
    [4] L. G. Khachiyan, A polynomial algorithm in linear programming, Sov. Math. Dokl., 20 (1979), 191–194.
    [5] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373–395. https://doi.org/10.1007/BF02579150 doi: 10.1007/BF02579150
    [6] M. Kojima, S. Mizuno, A. Yoshise, A primal-dual interior point algorithm for linear programming, In: Progress in mathematical programming: Interior point and related methods, New York: Springer, 1989, 29–47.
    [7] N. Megiddo, Pathways to the optimal set in linear programming, In: Progress in mathematical programming: interior-point and related methods, New York: Springer, 1989,131–158. https://doi.org/10.1007/978-1-4613-9617-8_8
    [8] S. Mizuno, M. Kojima, A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems, Math. Program., 44 (1989), 1–26. https://doi.org/10.1007/BF01587074 doi: 10.1007/BF01587074
    [9] F. L. Hitchcock, The distribution of a product from several sources to numerous localities, J. Math. Phys., 20 (1941), 224–230. https://doi.org/10.1002/SAPM1941201224 doi: 10.1002/SAPM1941201224
    [10] G. B. Dantzig, D. R. Fulkerson, S. M. Johnson, Solution of a large-scale traveling-salesman problem, Oper. Res., 2 (1954), 393–410. https://doi.org/10.1287/opre.2.4.393 doi: 10.1287/opre.2.4.393
    [11] L. R. Ford, D. R. Fulkerson, Maximal flow through a network, Canad. J. Math., 8 (1956), 399–404. https://doi.org/10.4153/CJM-1956-045-5 doi: 10.4153/CJM-1956-045-5
    [12] A. Ben-Tal, A. Nemirovski, Robust solutions of uncertain linear programs, Oper. Res. Lett., 25 (1999), 1–13. https://doi.org/10.1016/S0167-6377(99)00016-4 doi: 10.1016/S0167-6377(99)00016-4
    [13] S. Agrawal, Z. Wang, Y. Ye, A dynamic near-optimal algorithm for online linear programming, arXiv preprint, 2009, arXiv: 0911.2974. https://doi.org/10.48550/arXiv.0911.2974
    [14] S. S. Chen, D. L. Donoho, M. A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev., 43 (2001), 129–159. https://doi.org/10.1137/S003614450037906X doi: 10.1137/S003614450037906X
    [15] Y. Ye, The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate, Math. Oper. Res., 36 (2011), 593–603. https://doi.org/10.1287/moor.1110.0516 doi: 10.1287/moor.1110.0516
    [16] S. Mizuno, A strongly polynomial simplex method for totally unimodular LP, Optimization Online, Technical Report, 2014. Available at: https://optimization-online.org/wp-content/uploads/2014/07/4452.pdf
    [17] S. Fujishige, T. Hayashi, K. Yamashita, U. Zimmermann, Zonotopes and the LP-Newton method, Optim. Eng., 10 (2009), 193–205. https://doi.org/10.1007/s11081-008-9067-x doi: 10.1007/s11081-008-9067-x
    [18] T. Kitahara, S. Mizuno, J. Shi, The LP-Newton method for standard form linear programming problems, Oper. Res. Lett., 41 (2013), 426–429. https://doi.org/10.1016/j.orl.2013.05.004 doi: 10.1016/j.orl.2013.05.004
    [19] M. Tanaka, T. Okuno, Extension of the LP-Newton method to conic programming problems via semi-infinite representation, Numer. Algorithms, 86 (2021), 1285–1302. https://doi.org/10.1007/s11075-020-00933-6 doi: 10.1007/s11075-020-00933-6
    [20] T. Kitahara, N. Sukegawa, A simple projection algorithm for linear programming problems, Algorithmica, 81 (2019), 167–178. https://doi.org/10.1007/s00453-018-0436-3 doi: 10.1007/s00453-018-0436-3
    [21] Y. Matsuno, J. Shi, Rethinking linear programming: A new finite-termination LP-Newton approach, In: Advances in data science and optimization of complex systems, 1311 (2025), 76–82. https://doi.org/10.1007/978-3-031-90606-0_7
    [22] P. Wolfe, Finding the nearest point in a polytope, Math. Program., 11 (1976), 128–149. https://doi.org/10.1007/BF01580381 doi: 10.1007/BF01580381
    [23] S. Fujishige, P. Zhan, A dual algorithm for finding the minimum-norm point in a polytope, J. Oper. Res. Soc. Japan, 33 (1990), 188–195. https://doi.org/10.15807/jorsj.33.188 doi: 10.15807/jorsj.33.188
    [24] S. Fujishige, H. Sato, P. Zhan, An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane, Japan J. Ind. Appl. Math., 11 (1994), 245–264. https://doi.org/10.1007/BF03167224 doi: 10.1007/BF03167224
    [25] S. Fujishige, X. Liu, X. Zhang, An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set, J. Optim. Theory Appl., 105 (2000), 113–147. https://doi.org/10.1023/A:1004666028951 doi: 10.1023/A:1004666028951
    [26] K. Sekitani, Y. Yamamoto, Recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes, Math. Program., 61 (1993), 233–249. https://doi.org/10.1007/BF01582149 doi: 10.1007/BF01582149
    [27] S. Fujishige, T. Kitahara, L. A. Végh, An update-and-stabilize framework for the minimum-norm-point problem, Math. Program., 210 (2025), 281–311. https://doi.org/10.1007/s10107-024-02077-0 doi: 10.1007/s10107-024-02077-0
    [28] F. Bach, Learning with submodular functions: A convex optimization perspective, Found. Trends Mach. Learn., 6 (2013), 145–373. https://doi.org/10.1561/2200000039 doi: 10.1561/2200000039
    [29] S. Fujishige, Lexicographically optimal base of a polymatroid with respect to a weight vector, Math. Oper. Res., 5 (1980), 186–196. https://doi.org/10.1287/moor.5.2.186 doi: 10.1287/moor.5.2.186
    [30] S. Fujishige, Submodular functions and optimization, Amsterdam: North-Holland, 1991.
    [31] I. Shanu, C. Arora, P. Singla, Min norm point algorithm for higher order MRF-MAP inference, In: 2016 IEEE conference on computer vision and pattern recognition (CVPR), 2016, 5365–5374. https://doi.org/10.1109/CVPR.2016.579
    [32] E. Klafszky, J. Mayer, T. Terlaky, Linearly constrained estimation by mathematical programming, Eur. J. Oper. Res., 42 (1989), 254–267. https://doi.org/10.1016/0377-2217(89)90437-2 doi: 10.1016/0377-2217(89)90437-2
    [33] H. Takehara, An interior point algorithm for large scale portfolio optimization, Ann. Oper. Res., 45 (1993), 373–386. https://doi.org/10.1007/BF02282059 doi: 10.1007/BF02282059
    [34] J. A. De Loera, J. Haddock, A. Rademacher, The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential, SIAM J. Comput., 49 (2020), 138–169. https://doi.org/10.1137/18M1221072 doi: 10.1137/18M1221072
    [35] E. J. Candès, T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inf. Theory, 52 (2006), 5406–5425. https://doi.org/10.1109/TIT.2006.885507 doi: 10.1109/TIT.2006.885507
  • Reader Comments
  • © 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.1

Metrics

Article views(119) PDF downloads(6) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(3)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog