TARU PUBLICATIONS
Journal of Information and Optimization Sciences cover

Journal of Information and Optimization Sciences

(Since 1980)
Hybrid ·Peer-reviewed·ISSN (Online): 2169-0103·ISSN (Print): 0252-2667

WoS  JIF 2026 : 0.4 (Q4)

Powered by:Powered by

Monthly Journal: Publishes theoretical and applied research on topics in information and optimization sciences.

Issues up to 2022 co-published with and available at:Taylor & Francis
submissions@tarupublications.com
Taru Online First Current IssueSpecial IssuesBrowse all Issues
Journal of Information and Optimization Sciences
Open Access Research Article

A full Nesterov-Todd step feasible interior-point algorithm for semidefinite optimization based on a new hyperbolic barrier function

* ,

* Corresponding author · click or hover a name for details

pp. 1359–1376Vol. 47Issue 4April 2026DOI: 10.47974/JIOS-1604XML
Received:
01 Nov 2022
Published Online:
01 Apr 2026
Article type:
Research Article
Language:
EN
Article no.:
JIOS-1604
Pages:
1359–1376

Abstract

This study concerns solving semidefinite programming (SDP) problems using a new kernel-based primal-dual interior-point method (IPM). We propose a parameterized kernel function (KF) that has a hyperbolic barrier term. Taking advantage of the exponential convexity property of the new KF, we prove that the corresponding algorithm has a complexity of order O(√n log n log n/ε)  for large-update methods. To the best of our knowledge, this is the first hyperbolic KF for SDP to reach the best-known iteration bound for such methods. Preliminary numerical experiments indicate that the new KF is efficient compared with other existing KFs in the literature. 

Keywords

Semidefinite programmingInterior-point methodsKernel functionComplexity analysis

Subject Classifications

90C5190C22

References

[1] B. A. Hassan, Z. M. Abdullah, and S. A. Hussein, “Some new conjugate gradient methods for solving unconstrained optimization problems,” J. Inf. Optim. Sci., vol. 43, no. 4, pp. 893–903 (2022).
[2] G. Ma, H. Lin, and W. e. a. Jin, “Two modified conjugate gradient methods for unconstrained optimization with applications in image restoration problems,” J. Appl. Math. Comput., vol. 68, pp. 4733–4758 (2022).
[3] H. Mrad and S. M. Fakhari, “Optimization of unconstrained problems using a developed algorithm of spectral conjugate gradient method calculation,” Math. Comput. Simulation, vol. 215, pp. 282–290 (2024).
[4] Y. E. Nesterov and M. J. Todd, “Self-scaled barriers and interior-point methods for convex programming,” Math. Oper. Res., vol. 22, pp. 1–42 (1997).
[5] ——, “Primal-dual interior-point methods for self-scaled cones,” SIAM J. Optim., vol. 8, pp. 324–364 (1998).
[6] J. Peng, C. Roos, and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press (2002).
[7] Y. Q. Bai, M. El Ghami, and C. Roos, “A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization,” SIAM J. Optim., vol. 15, pp. 101–128  (2004).
[8] I. Touil and W. Chikouche, “Primal-dual interior point methods for semidefinite programming based on a new type of kernel functions,” Filomat, vol. 34, no. 12, pp. 3957–3969 (2020).
[9] ——, “Novel kernel function with a hyperbolic barrier term to primal-dual interior point algorithm for sdp problems,” Acta Math. Appl. Sin. Engl. Ser., vol. 38, pp. 44–67 (2022).
[10] S. Guerdouh, W. Chikouche, and I. Touil, “An efficient primal-dual interior point algorithm for linear optimization problems based on a novel parameterized kernel function with a hyperbolic barrier term,” (2021), halshs-03228790.
[11] S. Guerdouh, W. Chikouche, I. Touil, and A. Yassine, “Complexity of primal-dual interiorpoint algorithm for linear programming based on a new class of kernel functions,” Kybernetika, vol. 59, no. 6, pp. 827–860 (2024).
[12] S. Guerdouh, W. Chikouche, and I. Touil, “A primal-dual interior-point algorithm based on a kernel function with a new barrier term,” Stat. Optim. Inf. Comput., vol. 11, pp. 773–784 (2023).
[13] S. Guerdouh and W. Chikouche, “A primal-dual large-update interior-point algorithm for symmetric cone optimization based on a new class of kernel functions,” Palest. J. Math., vol. 13, no. 3, pp. 320–332 (2024).
[14] Y. Bouhenache, W. Chikouche, I. Touil, and S. Hafeshjani, “Complexity analysis of primal-dual interior point methods for convex quadratic programming based on a new twice parameterized kernel function,” J. Math. Model., vol. 12, no. 2, pp. 247–265 (2024).
[15] Y. Bouhenache, W. Chikouche, and I. Touil, “A large-update primal-dual interior-point algorithm for convex quadratic optimization based on a new bi-parameterized bi-hyperbolic kernel function,” Lobach. J. Math., vol. 45, no. 3, pp. 992–1007 (2024).
[16] Y. Bouhenache, W. Chikouche, and S. Guerdouh, “An interior-point algorithm for lcp based on a parameterized hyperbolic kernel function,” Comput. Math. Math. Phys., vol. 65, pp. 1181–1194 (2025).
[17] I. Touil, W. Chikouche, D. Benterki, and A. Zerari, “An efficient hyperbolic kernel function yielding the best known iteration bounds for linear programming,” Acta Math. Appl. Sin. Engl. Ser., vol. 41, pp. 133–151 (2025).
[18] M. J. Todd, K. C. Toh, and R. H. Tütüncü, “On the nesterov-todd direction in semidefinite programming,” SIAM J. Optim., vol. 8, pp. 769–796 (1998).
[19] M. El Ghami, Y. Q. Bai, and C. Roos, “Kernel-function based algorithms for semidefinite optimization,” RAIRO Oper. Res., vol. 43, pp. 189–199 (2009).
[20] M. El Ghami, Z. A. Guennoun, S. Bouali, and T. Steihaug, “Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term,” J. Comput. Appl. Math., vol. 236, pp. 3613–3623 (2012).
[21] C. Roos, T. Terlaky, and J. P. Vial, Theory and Algorithms for Linear Optimization, in: An Interior Point Approach. Chichester, UK: John Wiley and Sons (1997).
[22] G. Q. Wang, Y. Q. Bai, and C. Roos, “Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function,” J. Math. Model. Algorithms, vol. 4, pp. 409–433 (2005).
[23] M. R. Peyghami, S. F. Hafshejani, and L. Shirvani, “Complexity of interior point methods for linear optimization based on a new trigonometric kernel function,” J. Comput. Appl. Math., vol. 255, pp. 74–85 (2014).
[24] B. Kheirfam and M. Moslemi, “A polynomial-time algorithm for linear optimization based on a new kernel function with trigonometric barrier term,” Yugosl. J. Oper. Res., vol. 25, pp. 233–250 (2015).
[25] L. Derbal and Z. Kebbiche, “Theoretical and numerical result for linear optimization problem based on a new kernel function,” J. Sib. Fed. Univ. Math. Phys., vol. 12, no. 2, pp. 160–172 (2019).
[26] M. Li, M. Zhang, K. Huang, and Z. Huang, “A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function,” Optim. Eng., vol. 22, pp. 293–319 (2021).
[27] I. Touil, D. Benterki, and A. Yassine, “A feasible primal-dual interior point method for linear semidefinite programming,” J. Comput. Appl. Math., vol. 312, pp. 216–230 (2017).
[28] C. Roos, “A full-newton step O(n) infeasible interior-point algorithm for linear optimization,” SIAM J. Optim., vol. 16, no. 4, pp. 1110–1136 (2006).
[29] M. Moslemi and B. Kheirfam, “Complexity analysis of infeasible interior-point method for semidefinite optimization based on a new trigonometric kernel function,” Optim. Lett., vol. 13, pp. 127–145 (2019).
[30] S. Guerdouh, W. Chikouche, and B. Kheirfam, “A full-newton step infeasible interiorpoint algorithm based on a kernel function with a new barrier term,” J. Appl. Math. Comput., vol. 69, pp. 2935–2953 (2023).

Views: 177Downloads: 76Citations: 0