Geodesic
A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound
Communications in Mathematics, Tome 28 (2020) no. 1, pp. 27-41 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper, we propose a large-update primal-dual interior point algorithm for linear optimization. The method is based on a new class of kernel functions which differs from the existing kernel functions in which it has a double barrier term. The investigation according to it yields the best known iteration bound $O(\sqrt {n} \log (n) \log (\frac {n}{\varepsilon }) )$ for large-update algorithm with the special choice of its parameter $m$ and thus improves the iteration bound obtained in Bai et al.~\cite {El Ghami2004} for large-update algorithm.
In this paper, we propose a large-update primal-dual interior point algorithm for linear optimization. The method is based on a new class of kernel functions which differs from the existing kernel functions in which it has a double barrier term. The investigation according to it yields the best known iteration bound $O(\sqrt {n} \log (n) \log (\frac {n}{\varepsilon }) )$ for large-update algorithm with the special choice of its parameter $m$ and thus improves the iteration bound obtained in Bai et al.~\cite {El Ghami2004} for large-update algorithm.
Classification : 90C05, 90C31, 90C51
Keywords: Linear optimization; Kernel function; Interior point methods; Complexity bound 
@article{COMIM_2020_28_1_a2,
     author = {Ayache, Benhadid and Khaled, Saoudi},
     title = {A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound},
     journal = {Communications in Mathematics},
     pages = {27--41},
     year = {2020},
     volume = {28},
     number = {1},
     mrnumber = {4124288},
     zbl = {1465.90041},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/COMIM_2020_28_1_a2/}
}
TY  - JOUR
AU  - Ayache, Benhadid
AU  - Khaled, Saoudi
TI  - A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound
JO  - Communications in Mathematics
PY  - 2020
SP  - 27
EP  - 41
VL  - 28
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/COMIM_2020_28_1_a2/
LA  - en
ID  - COMIM_2020_28_1_a2
ER  - 
%0 Journal Article
%A Ayache, Benhadid
%A Khaled, Saoudi
%T A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound
%J Communications in Mathematics
%D 2020
%P 27-41
%V 28
%N 1
%U http://geodesic.mathdoc.fr/item/COMIM_2020_28_1_a2/
%G en
%F COMIM_2020_28_1_a2
Ayache, Benhadid; Khaled, Saoudi. A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound. Communications in Mathematics, Tome 28 (2020) no. 1, pp. 27-41. http://geodesic.mathdoc.fr/item/COMIM_2020_28_1_a2/

[1] Bai, Y.Q., Roos, C.: A primal-dual interior point method based on a new kernel function with linear growth rate. Proceedings of the 9th Australian Optimization Day, Perth, Australia, 2002, 14p,

[2] Bai, Y.Q., Ghami, M. El, Roos, C.: A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization. SIAM J. Optim., 15, 2004, 101-128, | DOI | MR

[3] Bouaafia, M., Benterki, D., Adnan, Y.: Complexity analysis of interior point methods for linear programming based on a parameterized kernel. RAIRO-Oper. Res., 50, 2016, 935-949, | DOI | MR

[4] Bouaafia, M., Benterki, D., Adnan, Y.: An efficient parameterized logarithmic kernel function for linear optimization. Optim. Lett., 12, 2018, 1079-1097, | DOI | MR

[5] Ghami, M. El: New Primal-Dual Interior-Point Methods Based on Kernel Functions. 2005, TU Delft, The Netherlands, PhD Thesis.

[6] Ghami, M. El, Ivanov, I.D., Roos, C., Steihaug, T.: A polynomial-time algorithm for LO based on generalized logarithmic barrier functions. Int. J. Appl. Math., 21, 2008, 99-115, | MR

[7] Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 4, 1984, 373-395, | MR

[8] Megiddo, N.: Pathways to the optimal set in linear programming. Progress in Mathematical Programming: Interior Point and Related Methods, 1989, 131-158, Springer, New York, | MR

[9] Peng, J., Roos, C., Terlaky, T.: A new and efficient large-update interior point method for linear optimization. J. Comput. Technol., 6, 2001, 61-80, | MR

[10] Peng, J., Roos, C., Terlaky, T.: A new class of polynomial primal-dual methods for linear and semidefinite optimization. European Journal of Operational Research, 143, 2002, 234-256, | DOI | MR

[11] Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms. 2002, Princeton University Press, Princeton, | MR

[12] Roos, C., Terlaky, T., Vial, J.P.: Theory and Algorithms for Linear Optimization, An Interior Point Approach. 1997, Wiley, Chichester, | MR

[13] Sonnevend, G.: An ``analytic center'' for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. System Modelling and Optimization: Proceedings of the 12th IFIP-Conference, Budapest, Hungary, Lecture Notes in Control and Information Science, 84, 1986, 866-876, Springer, Berlin, | MR

[14] Ye, Y.: Interior Point Algorithms, Theory and Analysis. 1997, Wiley, Chichester, | MR