Complexity analysis of primal-dual interior-point methods for convex quadratic programming based on a new twice parameterized kernel function

Bouhenache, Youssra; Chikouche, Wided; Touil, Imene; Fathi-Hafshejani, Sajad

doi:10.22124/jmm.2024.25394.2257

Complexity analysis of primal-dual interior-point methods for convex quadratic programming based on a new twice parameterized kernel function

Document Type : Research Article

Authors

¹ Laboratory of Pure and Applied Mathematics, Faculty of Exact Sciences and Informatics, University of Jijel, 18000 Jijel, Algeria

² Shiraz University of Technology, Fars 71557-13876, Shiraz, Iran

10.22124/jmm.2024.25394.2257

Abstract

In this paper, we present primal-dual interior-point methods (IPMs) for convex quadratic programming (CQP) based on a new twice parameterized kernel function (KF) with a hyperbolic barrier term. To our knowledge, this is the first KF with a twice parameterized hyperbolic barrier term. By using some conditions and simple analysis, we derive the currently best-known iteration bounds for large- and small-update methods, namely, $\textbf{O}\big(\sqrt{n}\log n\log\frac{n}{\epsilon}\big)$ and $\textbf{O}\big(\sqrt{n}\log\frac{n}{\epsilon}\big)$, respectively, with special choices of the parameters. Finally, some numerical results regarding the practical performance of the new proposed KF are reported.

Keywords

Main Subjects