Document Type : Research Article
Author
Laboratory of Science for Mathematics, Computer Science and Engineering Applications, Department of Mathematics, University Center of Barika, Amdoukal Road, Barika, 05001, Algeria
10.30473/coam.2026.75869.1339
Abstract
This paper introduces a novel parameterized kernel function for primal–dual interior-point methods (IPMs) applied to the linear optimization (LO) problem. The proposed kernel, governed by two parameters — a base u > 1 and a term-count ℓ ∈ N \ {0} — employs a multi-exponent power-sum structure (i.e., a sum of power terms with geometrically spaced exponents (u, u2, ..., uℓ) that decouples local curvature near the central path from asymptotic growth far from it. This decoupling is impossible with single-parameter kernels such as self-regular or trigonometric variants. Under mild, verifiable conditions, the resulting IPM attains a worst-case iteration complexity of O(uℓ n((uℓ +1)/2uℓ ) log(n/ϵ )) for large-update strategies, and O(u2ℓ √n log(n/ϵ )) for small-update strategies. Choosing u = (log n/2 )1/ℓ recovers the best-known large-update bound O(√n log(n) log(n/ϵ )). Numerical experiments on benchmark LP instances with dimensions up to n = 1000 confirm that the ℓ = 1, u = 3.5 variant consistently outperforms the classical self-regular kernel of Peng et al. in both iteration count and CPU time. The study demonstrates that self-regularity is sufficient but not necessary for optimal complexity, broadening the theoretical foundations of kernel-based interior-point frameworks.
Highlights
- A novel multi-parameter kernel function φ_ℓ(x) is introduced for primal–dual interior-point methods (IPMs) applied to linear optimization (LO), governed by two parameters: a base u > 1 and a term-count ℓ ∈ ℕ\{0}.
- The proposed kernel employs a multi-exponent power-sum structure that decouples local curvature near the central path from asymptotic growth far from it — a property unachievable by any single-parameter kernel such as self-regular or trigonometric variants.
- Worst-case iteration complexity bounds of O(u^ℓ · n^((u^ℓ+1)/(2u^ℓ)) · log(n/ε)) and O(u^(2ℓ) · √n · log(n/ε)) are rigorously established for large-update and small-update strategies, respectively.
- By selecting u = (log n / 2)^(1/ℓ), the method recovers the best-known O(√n log n · log(n/ε)) large-update complexity bound, demonstrating that self-regularity is sufficient but not necessary for optimal complexity.
- Numerical experiments on benchmark LP instances with dimensions up to n = 1000 confirm that the ℓ = 1, u = 3.5 variant consistently outperforms the classical self-regular kernel of Peng et al. in both iteration count and CPU time.
Keywords
- Primal-dual interior-point algorithms
- Large and small-update methods
- Parameterized kernel function
- Central path
- Complexity bounds
- Linear optimization
Main Subjects
[1] Amini, K., Haseli, A. (2007). “A new proximity function generating the best known iteration bounds for both large-update and small-update interior-point methods”. ANZIAM Journal, 49(2), 259–270. https://doi.org/10.1017/S1446181100012827
[2] Amrane, H., Fateh, M. (2025). “An efficient parametric kernel function of IPMs for linear optimization problems”. Results in Control and Optimization, 18, 100537. https://doi. org/10.1016/j.rico.2025.100537
[3] Bai, Y., El Ghami, M., Roos, K. (2004). “A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization”. SIAM Journal on Optimization, 15(1), 101–128. https://doi.org/10.1137/S1052623403423114
[4] Bai, Y., El Ghami, M., Roos, K. (2002). “A new efficient large-update primal-dual interior-point method based on a finite barrier”. SIAM Journal on Optimization, 13(3), 766–782.https://doi.org/10.1137/S1052623401398132
[5] Bai, Y.Q., Roos, C. (2003). “A polynomial-time algorithm for linear optimization based on a new simple kernel function”. Optimization Methods and Software, 18(6), 631–646.https://doi.org/10.1080/10556780310001639735
[6] Bouafia, M., Benterki, D., Yassine, A. (2018). “An efficient parameterized logarithmic kernel function for linear optimization”. Optimization Letters, 12(5), 1079–1097. https://doi.org/10.1007/s11590-017-1170-5
[7] Bouhenache, Y., Chikouche, W., Guerdouh, S. (2025). “An interior-point algorithm for LCP based on a parameterized hyperbolic kernel function”. Computational Mathematics and Mathematical Physics, 65(6), 1181–1194. https://doi.org/10.1134/ S096554252570054X
[8] Bounibane, B., Chalekh, R. (2024). “Kernel function-based primal-dual interior-point methods for linear optimization”. Palestine Journal of Mathematics, 13(4), 261–277. https://api.semanticscholar.org/CorpusID:279239371
[9] Bounibane, B., Guemmaz, A., Djeffal, E. L. (2022). “Theoretical and numerical result for linear semidefinite programming based on a new kernel function”. Journal of Mathematical and Computational Science, 12, 201. https://doi.org/10.28919/jmcs/7718
[10] Cho, G.M. (2011). “An interior point algorithm for linear optimization based on a new barrier function”. Applied Mathematics and Computation, 218(2), 386–395. https://doi.org/10.1016/j.amc.2011.05.075
[11] El Ghami, M. (2005). “New primal-dual interior-point methods based on kernel functions”. Doctoral Dissertation, Delft University of Technology, The Netherlands. http://resolver.tudelft.nl/uuid:0fa98a15-e579-4542-8c9f-cfecf3b64272
[12] El Ghami, M., Ivanov, I.D., Melissen, J.B.M., Roos, C., Steihaug, T. (2009). “A polynomial-time algorithm for linear optimization based on a new class of kernel functions”. Journal of Computational and Applied Mathematics, 224(2), 500–513. https://doi.org/10.1016/j.cam.2008.05.027
[13] El Ghami, M., Guennoun, Z.A., Bouali, S., Steihaug, T. (2012). “Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term”. Journal of Computational and Applied Mathematics, 236(15), 3613–3623. https://doi.org/ 10.1016/j.cam.2011.05.036
[14] Ibtissam, M., Randa, C., El Amir, D. (2025). “Complexity analysis of large-update interior-point methods for P*(κ)-HLCP based on a new parametric kernel function”. Statistics, Optimization and Information Computing, 14(1), 193–206. https://doi.org/10.19139/ soic-2310-5070-2345
[15] Karmarkar, N. (1984). “A new polynomial-time algorithm for linear programming”. Combinatorica, 4(4), 373–395. https://doi.org/10.1007/BF02579150
[16] Kojima, M., Mizuno, S., Yoshise, A. (1989). “A primal-dual interior point algorithm for linear programming”. In: Megiddo, N. (ed.) Progress in Mathematical Programming: Interior Point and Related Methods. Springer, New York, 29–47. https://doi.org/10.1007/978-1-4613-9617-8_2
[17] Lee, J., Cho, G.-M. (2024). “A new full-Newton step infeasible interior-point method for linear optimization”. Journal of Nonlinear and Convex Analysis, 25(12), 2991–3005. http://yokohamapublishers.jp/online2/opjnca/vol25/p2991.html
[18] Lesaja, G., Roos, C. (2010). “Unified analysis of kernel-based interior-point methods for P∗(κ)-linear complementarity problems”. SIAM Journal on Optimization, 20(6), 3014– 3039. https://doi.org/10.1137/090766735
[19] Megiddo, N. (1989). “Pathways to the optimal set in linear programming”. In: Megiddo, N. (ed.) Progress in Mathematical Programming: Interior Point and Related Methods. Springer, New York, 131–158. https://doi.org/10.1007/978-1-4613-9617-8_8
[20] Nesterov, Y.E., Nemirovskii, A.S. (1994). Interior Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia. https://doi.org/10.1137/1036175
[21] Peng, J., Roos, C., Terlaky, T. (2001). “A new and efficient large-update interior-point method for linear optimization”. Journal of Computational Technologies, 6(4), 61–80. https://optimization-online.org/?p=8564
[22] Peng, J., Roos, C., Terlaky, T. (2002). Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press. https://doi.org/10.1515/ 9781400825134
[23] Peyghami, M.R., Hafshejani, S.F. (2014). “Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function”. Numerical Algorithms, 67(1), 33–48. https://doi.org/10.1007/s11075-013-9772-1
[24] Roos, C., Terlaky, T., Vial, J.P. (1997). Theory and Algorithms for Linear Optimization: An Interior Point Approach. Wiley, Chichester.
[25] Sonnevend, G. (1986). “An ‘analytic center’ for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming”. Lecture Notes in Control and Information Science, 84, 866–876. Springer, Berlin. https://doi.org/10.1007/ BFb0043914
[26] Ye, Y. (1997). Interior point algorithms: Theory and analysis. John Wiley and Sons, New York. https://doi.org/10.1002/9781118032701.scard
)