An Interior Point Algorithm for Quadratic Programming Based on a New Step-Length

Article Sidebar

PDF
DOI: https://doi.org/10.28924/2291-8639-22-2024-233
Published: Dec 9, 2024
Cite as:
Assma Leulmi, Raouf Ziadi, Choubeila Souli, Mohammed A. Saleh, Abdulgader Z. Almaymuni, An Interior Point Algorithm for Quadratic Programming Based on a New Step-Length, Int. J. Anal. Appl., 22 (2024), 233.

Main Article Content

Assma Leulmi, Raouf Ziadi, Choubeila Souli, Mohammed A. Saleh, Abdulgader Z. Almaymuni

Abstract

Interior point methods have seen significant advancements in recent decades for solving linear, semi-definite and quadratic programming. Among these methods, the logarithmic barrier methods based on approximate functions have polynomial convergence and are known for their favorable numerical performance. In this work, a new minorant function for the barrier method is proposed for solving convex quadratic problems with inequality constraints. The proposed minorant function allows to compute the steplength easily and quickly, unlike the line search method, which is computationally intensive and time-consuming. Mathematical results concerning the convergence of the algorithm are established. The numerical comparisons with the inexact Wolfe line search technique show that the proposed method is promising and effective.

Article Details

References

  1. M. Achache, A New Primal-Dual Path-Following Method for Convex Quadratic Programming, Comput. Appl. Math. 25 (2006), 97-110. https://doi.org/10.1590/S0101-82052006000100005.
  2. M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear Programming: Theory and Algorithms, 3rd ed, WileyInterscience, Hoboken, 2006. https://doi.org/10.1002/0471787779.
  3. N. Boudjellal, H. Roumili, Dj. Benterki, A Primal-Dual Interior Point Algorithm for Convex Quadratic Programming Based on a New Parametric Kernel Function, Optimization 70 (2021), 1703–1724. https://doi.org/10.1080/02331934.2020.1751156.
  4. J.F. Bonnans, ed., Numerical Optimization: Theoretical and Practical Aspects, Springer, 2003.
  5. S. Chaghoub, D. Benterki, A Logarithmic Barrier Method Based on a New Majorant Function for Convex Quadratic Programming, IAENG Int. J. Appl. Math. 51 (2021), 1-6.
  6. A. Chikhaoui, B. Djebbar, A. Belabbaci, A. Mokhtari, Optimization of a Quadratic Function under Its Canonical Form, Asian J. Appl. Sci. 2 (2009), 499-510.
  7. J.P. Crouzeix, B. Merikhi, A Logarithm Barrier Method for Semi-Definite Programming, RAIRO - Oper. Res. 42 (2008), 123–139. https://doi.org/10.1051/ro:2008005.
  8. A. Leulmi, B. Merikhi, D. Benterki, Study of a Logarithmic Barrier Approach for Linear Semidefinite Programming, J. Sib. Fed. Univ. Math. Phys. 11 (2018), 1–13.
  9. A. Leulmi, S. Leulmi, Logarithmic Barrier Method via Minorant Function for Linear Programming, J. Sib. Fed. Univ. Math. Phys. 12 (2019), 191–201.
  10. L. Menniche, D. Benterki, A Logarithmic Barrier Approach for Linear Programming, J. Comput. Appl. Math. 312 (2017), 267–275. https://doi.org/10.1016/j.cam.2016.05.025.
  11. M.A. Saleh, Enhancing Deep Learning Optimizers for Detecting Malware Using Line Search Method under Strong Wolfe Conditions, in: 2023 3rd International Conference on Computing and Information Technology (ICCIT), IEEE, Tabuk, Saudi Arabia, 2023: pp. 222–226. https://doi.org/10.1109/ICCIT58132.2023.10273908.
  12. C. Souli, R. Ziadi, I. Lakhdari, A. Leulmi, An Efficient Hybrid Conjugate Gradient Method for Unconstrained Optimization and Image Restoration Problems, Iran. J. Numer. Anal. Optim. in Press.
  13. Y. Ye, E. Tse, An Extension of Karmarkar’s Projective Algorithm for Convex Quadratic Programming, Math. Program. 44 (1989), 157–179. https://doi.org/10.1007/BF01587086.
  14. Y. Ye, E. Tse, A Polynomial Algorithm for Convex Quadratic Programming, Stanford University, (1986).
  15. H. Wolkowicz, G.P.H. Styan, Bounds for Eigenvalues Using Traces, Linear Algebra Appl. 29 (1980), 471–506. https://doi.org/10.1016/0024-3795(80)90258-X.
  16. Z. Billel, B. Djamel, K. Aicha, R. Hadjer, Interior-Point Algorithm for Linear Programming Based on a New Descent Direction, RAIRO - Oper. Res. 57 (2023), 2473–2491. https://doi.org/10.1051/ro/2023127.
  17. R. Ziadi, A. Bencherif-Madani, A Perturbed Quasi-Newton Algorithm for Bound-Constrained Global Optimization, J. Comput. Math. 43 (2025), 143–173. https://doi.org/10.4208/jcm.2307-m2023-0016.