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

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

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

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


[1] M. Achache, Complexity analysis of an interior point algorithm for the semidefinite optimization
based on a kernel function with a double barrier term, Acta Math. Sin. Engl. 31 (2015) 543–556.
[2] Y.Q. Bai, M. El Ghami, C. Roos, A comparative study of kernel functions for primal-dual interior
point algorithms in linear optimization, SIAM. J. Optim. 15 (2004) 101–128.
[3] Y.Q. Bai, G. Lesaja, C. Roos, G.Q. Wang, M. El Ghami, A class of large-update and small-update
primal-dual interior-point algorithms for linear optimization, J. Optim. Theory Appl. 138 (2008)
341–359.
[4] M. Bouafia, A. Yassine, An efficient twice parameterized trigonometric kernel function for linear
optimization, Optim. Engin. 21 (2020) 651–672.
[5] M. Bouafia, A. Yassine, Complexity analysis of primal-dual interior-point methods for linear opti-
mization based on a new and efficient bi-parameterized kernel function with a trigonometric barrier
term, RAIRO Oper. Res. 56 (2022) 732–750.
[6] N. Boudjellal, H. Roumili, D. Benterki, Complexity analysis of interior point methods for convex
quadratic programming based on a parameterized kernel function, Bol. Soc. Parana. Mat. 40 (2022)
1–16.
[7] N. Boudjellal, H. Roumili, D. Benterki, A primal-dual interior point algorithm for convex
quadratic programming based on a new parametric kernel function, Optim. 70 (2021) 1703–1724.
[8] Y. Bouhenache, W. Chikouche, 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., to appear.
[9] X. Cai, G. Wang, Z. Zhang, Complexity analysis and numerical implementation of primal-dual
interior-point methods for convex quadratic optimization based on a finite barrier, Numer. Algo-
rithms 62 (2013) 289–306.
[10] Y.Y. Cho, G.M. Cho, A Large-update interior point algorithm for P∗(κ) lcp based on a new kernel
function, East Asian Math. J. 26 (2010) 9–23.
[11] M. El Ghami, I. Ivanov, J.B.M. Melissen, C. Roos, T. Steihaug, A polynomial-time algorithm for
linear optimization based on a new class of kernel functions, J. Comput. Appl. Math. 224 (2009)
500–513.
[12] M. El Ghami, Z.A. Guennoun, S. Bouali, T. Steihaug, Interior-point methods for linear optimization
based on a kernel function with a trigonometric barrier term, J. Comput. Appl. Math. 236 (2012)
3613–3623.
[13] S.F. Hafshejani, H. Mansouri, M.R. Peyghami, S. Chen, Primaldual interior-point method for
linear optimization based on a kernel function with trigonometric growth term, Optim. 67 (2018)
1605–1630.
[14] N.K. Karmarkar, A new polynomial-time algorithm for linear programming, In: Proceedings of
the 16th Annual ACM Symposium on Theory of Computing (4) (1984) 373–395.
[15] B. Kheirfam, M. Moslemi, A plynomial-time algorithm for linear optimization based on a new
kernel function with trigonometric barrier term, Yugoslav J. Oper. Res. 25 (2015) 233–250.
[16] M. Kojima, S. Mizuno, A. Yoshise, A Primal-Dual Interior Point Algorithm for Linear Program-
ming, Progress in Mathematical Programming: Interior-Point and Related Methods, Springer Ver-
lag, New York, 29–47,1989.
[17] Y.H. Lee, J.H. Jin, G.M. Cho, Kernel function based interior-point algorithms for semidefinite
optimization, Math. Ineq. Appl. 4 (2013) 1279–1294.
[18] N. Megiddo, Pathways to the optimal set in linear programming, In Progress in mathematical
programming: Interior-point and related methods, Springer-Verlag, New York, 131–158, 1989.
[19] Y.E. Nesterov, A.S. Nemirovskii, Interior Point Polynomial Algorithms in Convex Programming,
SIAM Studies in Applied Mathematics, SIAM, Philadelphia, 1994.
[20] J. Peng, C. Roos, T. Terlaky, A new and efficient large-update interior point method for linear
optimization, J. Comput. Technol. 6 (2001) 61–80.
[21] J. Peng, C. Roos, T. Terlaky, Self-regularity: A new Paradigm for Primal-Dual Interior-Point
Algorithms, Princeton University Press, Princeton, NJ, 2002.
[22] M.R. Peyghami, K. Amini, A kernel function based interior-point methods for solving P∗(k)-linear
complementarity problem, Acta Math. Sinica (Engl. Ser.) 26 (2010) 1761–1778.
[23] S. Guerdouh, W. Chikouche, 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, HAL Id: halshs-03228790.
[24] S. Guerdouh, W. Chikouche, I. Touil, A primal-dual interior-point algorithm based on a kernel
function with a new barrier term, Stat. Optim. Inf. Comput. 11 (2023) 773–784.
[25] G.M. Cho,Y.Y. Cho, Y.H. Lee A primal-dual interior-point algorithm based on a kernel function,
The ANZIAM J. 51 (4) (2010) 476–491.
[26] M.R. Peyghami, An interior point approach for semidefinite optimization using new proximity
functions, Asia-Pac. J. Oper. Res. 26 (2009) 365–382.
[27] G.Q. Wang, Y.Q. Bai, Y. Liu, M. Zhang, A new primal-dual interior-point algorithm for convex
quadratic optimization, J. Shanghai Univ. 12 (2008) 189–196.
[28] I. Touil, W. Chikouche, Primal-dual interior point methods for semidefinite programming based
on a new type of kernel functions, Filomat 34 (2020) 3957–3969.
[29] I. Touil, W. Chikouche, Novel kernel function with a hyperbolic barrier term to primal-dual interior
point algorithm for SDP problems, Acta Math. Sinica (Engl. Ser.) 38 (2022) 44–67.
[30] I. Touil, D. Benterki, A primal-dual interior-point method for the semidefinite programming prob-
lem based on a new kernel function, J. Nonlinear Funct. Anal. 25 (2019).
[31] A. Zerari, D. Benterki, A new efficient primal-dual projective interior point method for semidefinite
programming, J. Nonlinear Funct. Anal. 12 (2019).