Open Access
Research Article
Efficient descent direction of a primal-dual interior point algorithm for convex quadratic optimization
*Billel ZaouiCorresponding authorbillel.zaoui@univ-setif.dzDepartment of Mathematics Laboratory of Fundamental and Numerical Mathematics Faculty of Sciences University of Ferhat Abbas Setif-119000, AlgeriaView full profile → , Dj. Benterkidjbenterki@univ-setif.dzDepartment of Mathematics Laboratory of Fundamental and Numerical Mathematics Faculty of Sciences University of Ferhat Abbas Setif-1Department of Mathematics Laboratory of Fundamental and Numerical Mathematics Ferhat Abbas UniversitySetif, 19000, AlgeriaView full profile → , Samia Khelladisamia.boukaroura@univ-setif.dzDepartment of Mathematics Laboratory of Fundamental and Numerical Mathematics Faculty of Sciences University of Ferhat Abbas Setif-1Ferhat Abbas, 19000, AlgeriaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 12 Jul 2022
- Published Online:
- 01 Jan 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-1463
- Pages:
- 99–117
Abstract
We introduce a new interior-point method for solving convex quadratic programming under full-Newton step. The method involves an equivalent algebraic transformation applied to the system defining the central path. This approach provides an efficient search direction for the considered algorithm. Furthermore, we show that the introduced method produces an optimal solution within polynomial time. The established numerical tests conclude that the newly proposed algorithm is not only polynomial but requires a number of iterations clearly lower than that obtained theoretically.
Keywords
Subject Classifications
90C2090C51
References
[1] M. Achache, “A new primal-dual path-following method for convex quadratic programming,” Comput. Appl. Math., vol. 25, no. 1, pp. 97–110 (2006).[2] M. Achache and M. Goutali, “A primal-dual interior point algorithm for convex quadratic programs,” Stud. Univ. Babeş-Bolyai Math. Series Informatica, vol. LVII, no. 1, pp. 48–58 (2012).[3] M. Achache, “A weighted path-following method for the linear complementarity problem,” Stud. Univ. Babeş-Bolyai Math. Series Informatica, vol. 49, no. 1, pp. 61–73 (2004).[4] 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, no. 1, pp. 101–128 (2005).[5] M. Bouafia, D. Benterki, and A. Yassine, “Complexity analysis of interior point methods for linear programming based on a parameterized kernel function,” RAIRO Oper. Res., vol. 50, pp. 935–949 (2016).[6] M. Bouafia, D. Benterki, and A. Yassine, “An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a trigonometric barrier term,” J. Optim. Theory Appl., vol. 170, no. 2, pp. 528–545 (2016).[7] N. Boudjellal, H. Roumili, and D. Benterki, “A primal-dual interior point algorithm for convex quadratic programming based on a new parametric kernel function,” Optimization, vol. 70, no. 8, pp. 1703–1724 (2021).[8] Zs. Darvay, “New interior point algorithms in linear programming,” Adv. Model. Optim., vol. 5, no. 1, pp. 51–92 (2003).[9] Zs. Darvay, I. M. Papp, and P. R. Takács, “Complexity analysis of a full-Newton step interior-point method for linear optimization,” Period. Math. Hungar., vol. 73, no. 1, pp. 27–42 (2016).[10] Zs. Darvay and P. R. Takács, “New method for determining search directions for interior-point algorithms in linear optimization,” Optim. Lett., vol. 12, pp. 1099–1116 (2018).[11] M. El Ghami, Z. Guennoun, S. Bouali, M. F. M. El Moudni, A. G. Hammad, and A. A. B. Elhaj, “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).[12] Z. Feng and L. Fang, “A wide neighborhood interior-point method with iteration-complexity bound for semidefinite programming,” Optimization, vol. 59, no. 8, pp. 1235–1246 (2010).[13] B. Kheirfam, M. Moslem, “A polynomial-time algorithm for linear optimization based on a new kernel function with trigonometric barrier term,” Yugosl. J. Oper. Res., vol. 25, no. 2, pp. 233–250 (2015).[14] X. Li and M. Zhang, “Interior-point algorithm for linear optimization based on a new trigonometric kernel function,” Oper. Res. Lett., vol. 43, no. 5, pp. 471–475 (2015).[15] M. Peyghami, S. 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).[16] C. Roos, T. Terlaky, and J. Ph. Vial, Theory and Algorithms for Linear Optimization, An Interior Point Approach, Wiley, Chichester (1997).[17] G. Sonnevend, “An analytic center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming,” in Lect. Notes Control Inf. Sci., A. Prekopa, J. Szelezsan, and B. Strazicky, Eds., vol. 84, pp. 866–876 (1986).[18] S. M. Stefanov, “On the solution of quadratic programming problem with a feasible region defined as a Minkowski sum of a compact set and finitely generated convex closed cone,” J. Inf. Optim. Sci., vol. 39, no. 6, pp. 1223–1230 (2018), doi: 10.1080/02522667.2017.1317956.[19] G. Wang and Y. Bai, “A new primal-dual path-following interior-point algorithm for semidefinite optimization,” J. Math. Anal. Appl., vol. 353, no. 1, pp. 339–349 (2009).[20] G. Wang and Y. Bai, “A primal-dual path-following interior-point algorithm for second-order cone optimization with full Nesterov-Todd step,” Appl. Math. Comput., vol. 215, no. 3, pp. 1047–1061 (2009).[21] G. Wang and Y. Bai, “A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization,” J. Optim. Theory Appl., vol. 154, no. 3, pp. 966–985 (2012).[22] S. J. Wright, Primal-dual interior point methods, SIAM (1997).[23] L. Zhang and Y. Xu, “A full-Newton step interior-point algorithm based on modified Newton direction,” Oper. Res. Lett., vol. 39, pp. 318–322 (2011).
Views: 147Downloads: 10Citations: 0
