A simplicial homology interior-point algorithm for nonlinear programming

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, The University of Jordan, Amman, Jordan

Abstract

In this paper, we investigate the use of computational algebraic topology and simplicial homology within the framework of Sperner’s lemma to solve box- and inequality-constrained nonlinear (nonconvex) programming problems. The homology clustering method we consider provides optimal or near-optimal candidate solutions of locally convex subdomains in the search space by estimating the homology groups of a complex constructed on a hypersurface that is homeomorphic to a complex on the objective function. Each candidate point is then chosen as a starting point for a local iterative interior-point optimization technique that performs well on the corresponding locally convex subdomain. The best solution obtained from executing parallel interior-point techniques is the global optimal solution of the problem over the nonconvex domain. In addition, we compare the proposed method with the existing topographical interior-point approach and other solvers across various test problems. The computational results demonstrate that the simplicial interior-point algorithm performs well in finding the global minimum and outperforms both the topographical interior-point algorithm and the MIDACO solver in practice.

Keywords

Main Subjects

References

[1] H. Abedi and B. Kheirfam, An efficient second-order predictor–corrector infeasible primal–dual IPM algorithm with large iteration path updates for solving well-known SDO problems, J. Comput. Appl. Math. 459 (2025), no. C, 116379.
https://doi.org/10.1016/j.cam.2024.116379
[2] M.M. Ali, C. Khompatraporn, and Z.B. Zabinsky, A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems, J. Global Optim. 31 (2005), 635–672. https://doi.org/10.1007/s10898-004-9972-2
[3] B. Alzalg, Combinatorial and Algorithmic Mathematics: From Foundation to Optimization, John Wiley and Sons, 2024.
[4] P. Belotti, J. Lee, L. Liberti, F. Margot, and A. Wächter, Branching and bounds tighteningtechniques for non-convex MINLP, vol. 24, Taylor and Francis, Inc., USA, 2009.
[5] E.K.P. Chong and S.H. Żak, An Introduction to Optimization, John Wiley and Sons, 2008.
[6] A. Dekkers and E. Aarts, Global optimization and simulated annealing, Math. Program. 50 (1991), no. 1, 367–393.
https://doi.org/10.1007/BF01594945
[7] S.C Endres, C. Sandrock, and W.W. Focke, A simplicial homology algorithm for Lipschitz optimisation, J. Global Optim. 72 (2018), no. 2, 181–217. https://doi.org/10.1007/s10898-018-0645-y
[8] C. Floudas and P.M. Pardalos, Recent Advances in Global Optimization, Princeton University Press, 1992.
[9] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley series in artificial intelligence, Addison-Wesley, 1989.
[10] A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, 2002.
[11] N. Henderson, M. de Sá Rêgo, W.F. Sacco, and R.A. Rodrigues Jr, A new look at the topographical global optimization method and its application to the phase stability analysis of mixtures, Chemical Engineering Science 127 (2015), 151-174. https://doi.org/10.1016/j.ces.2015.01.029
[12] M. Henle, A Combinatorial Introduction to Topology, Dover, New York, NY, 1994.
[13] J. Herskovits, Feasible direction interior-point technique for nonlinear optimization, J. Optim. Theory Appl. 99 (1998), no. 1, 121–146. https://doi.org/10.1023/A:1021752227797
[14] W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag, Berlin, Heidelberg, 1981.
[15] J. Kennedy and R. Eberhart, Particle swarm optimization, Proceedings of ICNN’95 - International Conference on Neural Networks, vol. 4, 1995, pp. 1942–1948. https://doi.org/10.1109/ICNN.1995.488968
[16] B. Kheirfam, A. Nasrollahi, and M. Mohammadi, A second-order corrector infeasible interior-point method for semidefinite optimization based on a wide neighborhood, J. Sci. Comput. 86 (2021), no. 1, 13. https://doi.org/10.1007/s10915-020-01384-w
[17] T.T. Lu and S.H. Shiou, Inverses of $2\times 2$ block matrices, Computers and Mathematics with Applications 43 (2002), no. 1-2, 119–129.
[18] D.G. Luenberger, Introduction to Linear and Nonlinear Programming, Addison-Wesley Pub. Co., Reading, Mass, 1973.
[19] J. Nocedal and S.J. Wright, Numerical Optimization, Springer Series in Operations Research and Financial Engineering, pp. 1–664, Springer Nature, 2006.
[20] E.R. Panier, A.L. Tits, and J.N. Herskovits, Feasible direction interior-point technique for nonlinear optimization, SIAM J. Control Optim. 24 (1988), no. 4, 788–811. https://doi.org/10.1137/0326046
[21] G. Petelin, G. Cenikj, and T. Eftimov, Tinytla: Topological landscape analysis for optimization problem classification in a limited sample setting, Swarm and Evolutionary Computation 84 (2024), 101448. https://doi.org/10.1016/j.swevo.2023.101448
[22] M.J.D. Powell, The convergence of variable metric methods for nonlinearly constrained optimization calculations, In Nonlinear Programming 3, Proceedings of the Special Interest Group on Mathematical Programming Symposium (University of Wisconsin–Madison), Elsevier, 1978, pp. 27–63.
[23] E. Sperner, Neuer beweis für die invarianz der dimensionszahl und des gebietes, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 6 (1928), no. 1, 265–272. https://doi.org/10.1007/BF02940617
[24] R. Storn and K. Price, Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim. 11 (1997), no. 4, 341–359. https://doi.org/10.1023/A:1008202821328
[25] F. Zhang, Matrix Theory: Basic Results and Techniques, Universitext, Springer New York, 2011.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 08 May 2026

Files

Share

How to cite

Statistics