Complexity Analysis of an Interior-point Algorithm for CQP Based on a New Parametric Kernel Function

Randa Chalekh; El Amir Djeffal

doi:10.19139/soic-2310-5070-1761

Randa Chalekh Mathematics Department, University of Batna 2, Algeria
El Amir Djeffal LEDPA Laboratory, Mathematics Department, University of Batna 2, Batna

DOI: https://doi.org/10.19139/soic-2310-5070-1761

Keywords: Convex quadratic programmin, kernel functio, interior-point method, iteration boun

Abstract

In this paper, we present a primal-dual interior-point algorithm for convex quadratic programming problem based on a new parametric kernel function with a hyperbolic-logarithmic barrier term. Using the proposed kernel function we show some basic properties that are essential to study the complexity analysis of the correspondent algorithm which we find coincides with the best know iteration bounds for the large-update method, namely, $O\left(\sqrt{n} \log n \log\frac{n}{\varepsilon}\right)$ by a special choice of the parameter $p>1$.

References

N.Karmarkar, A new polynomial-time algorithm for linear programming. In Proceeding of the 16th Annual ACM. Symposium on theory of computing, pages 303-311, (1984).

C.Roos, T.Terlaky, J.-Ph.Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley & Sons, Chichester, UK, (1997), 2nd Ed, Springer, (2006).

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, 101-128 (2004).

E.A. Djeffal, M. Laouar, A primal-dual interior-point method based on a new kernel function for linear complementarity problem, Asian-European Journal of Mathematics 12 (07), 2050001, 2019

E.A. Djeffal, B. Bounibane, Kernel function based interior point algorithms for linear optimization, International Journal of Mathematical Modelling and Numerical Optimisation, 158-177, 2019

E.A. Djeffal, L. Djeffal, A path following interior-point algorithm for semidefinite optimization problem based on new kernel function, Journal of Mathematical Modeling 4 (1), 35-58, 2016.

E.A. Djeffal, B. Bounibane, A. Guemmaz, Theoretical and numerical result for linear semidefinite programming based on a new kernel function, J. Math. Comput. Sci. (http://scik.org), 12, 2022.

M.W.Zhang, A large-update interior-point algorithm for convex quadratic semidefinite optimization based on a new kernel function. Acta Mathematica Sinica, English Series, vol.28 : 2313-2321, (2012).

M.R.Peyghami & S.F.Hafshejani, Complexity analysis of an Interior point algorithm for linear optimisation based on a new proximity function. Numerical-Algorithms, 67 : 33-48, (2014).

M.R.Peyghami, S.F.Hafshejani, An interior point algorithm for solving convex quadratic semidefinite optimization problems using a new kernel function. Iranian J Math Sci Inform. 12 : 131–152, (2017).

M.Achache Complexity analysis of an interior point algorithm for the semidefinite optimization based on a new kernel function with a double barrier term. Acta Mathematica Sinica, English Series, 31 (3) : 543-556, (2015).

El.A.Djeffal, M.Laouar, A primal-dual interior-point method based on a new kernel function for linear complementarity problem, Asian-European, (2018).

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, 3613–3623, (2012).

M.Bouafia, D.Benterki, 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. 170, 528–545, (2016).

J.Peng, C.Roos, and T.Terlaky, Self-Regularity A New Paradigm for Primal-Dual Interior-Point Algorithms, Princeton University Press, Princeton, NJ, (2002).

M.Kojima, M.Shindoh , S.Hara, Interior point methods for the monotone semidefinite linear complementarity in symmetric matrices. SIAM J Optim. (1997); 7:86–125.