A Primal-Dual Interior-Point Algorithm Based on a Kernel Function with a New Barrier Term
Abstract
In this paper, we propose a path-following interior-point method (IPM) for solving linear optimization (LO) problems based on a new kernel function (KF). The latter differs from other KFs in having an exponential-hyperbolic barrier term that belongs to the hyperbolic type, recently developed by I. Touil and W. Chikouche \cite{filomat2021,acta2022}. The complexity analysis for large-update primal-dual IPMs based on this KF yields an $\mathcal{O}\left( \sqrt{n}\log^2n\log \frac{n}{\epsilon }\right)$ iteration bound which improves the classical iteration bound. For small-update methods, the proposed algorithm enjoys the favorable iteration bound, namely, $\mathcal{O}\left( \sqrt{n}\log \frac{n}{\epsilon }\right)$. We back up these results with some preliminary numerical tests which show that our algorithm outperformed other algorithms with better theoretical convergence complexity. To our knowledge, this is the first feasible primal-dual interior-point algorithm based on an exponential-hyperbolic KF.References
K. Amini and K. A. Haseli, A new proximity function generating the best known iteration bounds for both large-update and small-update interior-point methods, ANZIAM Journal, vol. 49, pp. 259–270, 2007.
N. Anane, M´ethodes de points int´erieurs pour la programmation lin´eaire bas´ees sur les fonctions noyaux, (Magister thesis), Ferhat Abbas University, Setif, Algeria, 2012.
Y. Q. Bai, M. El ghami and C. Roos, A new efficient large-update primal-dual interior-point method based on a finite barrier, SIAM Journal on Optimization, vol. 13, pp. 766–782, 2003.
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 Journal on Optimization, vol. 15, no. 1, pp. 101–128, 2004.
Y. Q. Bai, J. L. Guo and C. Roos, A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms, Acta Mathematica Sinica, English Series, vol. 25, no. 12, pp. 2169–2178, 2009.
M. Bouafia and A. Yassine, An efficient twice parameterized trigonometric kernel function for linear optimization, Optimization and Engineering, vol. 21, pp. 651–672, 2020.
Z. darvay, A new algorithm for solving self-dual linear optimization problems, Studia Universitatis Babes-Bolyai: Series Informatica, vol. 47, no. 1, pp. 15–26, 2002.
Z. Darvay, T. Ill´es and P. Rig´o , Predictor-corrector interior-point algorithm for P∗(κ)−linear complementarity problems based on a new type of algebraic equivalent transformation technique, European Journal of Operational Research, vol. 298, no. 1, pp. 25–35, 2022.
L. Derbal and Z. Kebbiche, Theoretical and numerical result for linear optimization problem based on a new kernel function, Journal of Siberian Federal University. Mathematics & Physics, vol. 12, no. 2, pp. 160–172, 2019.
S. Fathi Hafshejani and Z. Moaberfard, An interior-point algorithm for linearly constrained convex optimization based on kernel function and application in non-negative matrix factorization, Optimization and Engineering, vol. 21, pp. 1019–1051, 2020.
S. Guerdouh, W. Chikouche and 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. halshs-03228790
L. Guerra and M. Achache, A parametric kernel function generating the best known iteration bound for large-update methods for CQSDO, Statistics, Optimization & Information Computing, vol. 8, no. 4, pp. 876–889, 2020.
N. K. Karmarkar, A new polynomial-time algorithm for linear programming, In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, vol. 4, pp. 373–395, 1984.
A. Keraghel, Etude adaptative et comparative des principales variantes dans l’algorithme de Karmarkar, (Ph.D. thesis), Joseph Fourier University, Grenoble I, France, 1989.
B. kheirfam, Corrector-predictor interior-point method with new search direction for semidefinite optimization, Journal of Scientific Computing, vol. 95, no. 10, 2023.
M. Li, M. Zhang, K. Huang and Z. Huang, A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function, Optimization and Engineering, vol. 22, pp. 293–319, 2021.
N. Moussaoui and M. Achache, A weighted-path following interior-point algorithm for convex quadratic optimization Based on modified search directions, Statistics, Optimization & Information Computing, vol. 10, no. 3, pp. 873–889, 2022.
J. Peng, C. Roos and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite optimization, European Journal of Operational Research, vol. 143, pp. 234–256, 2002.
J. Peng, C. Roos and T. Terlaky, Self-Regularity: A new paradigm for primal-dual interior-point algorithms, Princeton University Press, 2002.
M. Reza Peyghami, S. Fathi Hafshejani and L. Shirvani, Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function, Journal of Computational and Applied Mathematics, vol. 255, pp. 74–85, 2014.
C. Roos, T. Terlaky and J. Ph. Vial, Theory and algorithms for linear optimization, in: An interior point Approach, John Wiley and Sons, Chichester, UK, 1997.
I. Touil and W. Chikouche, Primal-dual interior point methods for semidefinite programming based on a new type of kernel functions, Filomat, vol. 34, no. 12, pp. 3957–3969, 2020.
I. Touil and W. Chikouche, Novel kernel function with a hyperbolic barrier term to primal-dual interior point algorithm for SDP problems, Acta Mathematica Sinica, English Series, vol. 38, no. 1, pp. 44–67, 2022.
I. Touil and D. Benterki, A primal-dual interior-point method for the semidefinite programming problem based on a new kernel function, Journal of Nonlinear Functional Analysis, Art. ID 25, 2019.
I. Touil, D. Benterki and A. Yassine, A feasible primal-dual interior point method for linear semidefinite programming, Journal of Computational and Applied Mathematics, vol. 312, pp. 216–230, 2017.
D. Zhao and M. Zhang, A primal-dual large-update interior-point algorithm for semi-definite optimization based on a new kernel function, Statistics, Optimization & Information Computing, vol. 1, no. 1, pp. 41-61, 2013.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
