A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound

Benhadid Ayache; Saoudi Khaled

Communications in Mathematics (2020)

  • Volume: 28, Issue: 1, page 27-41
  • ISSN: 1804-1388

Abstract

top
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 ( n log ( n ) log ( n ε ) ) for large-update algorithm with the special choice of its parameter m and thus improves the iteration bound obtained in Bai et al. [El Ghami2004] for large-update algorithm.

How to cite

top

Ayache, Benhadid, and 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 28.1 (2020): 27-41. <http://eudml.org/doc/297120>.

@article{Ayache2020,
abstract = {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. [El Ghami2004] for large-update algorithm.},
author = {Ayache, Benhadid, Khaled, Saoudi},
journal = {Communications in Mathematics},
keywords = {Linear optimization; Kernel function; Interior point methods; Complexity bound},
language = {eng},
number = {1},
pages = {27-41},
publisher = {University of Ostrava},
title = {A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound},
url = {http://eudml.org/doc/297120},
volume = {28},
year = {2020},
}

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
PB - University of Ostrava
VL - 28
IS - 1
SP - 27
EP - 41
AB - 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. [El Ghami2004] for large-update algorithm.
LA - eng
KW - Linear optimization; Kernel function; Interior point methods; Complexity bound
UR - http://eudml.org/doc/297120
ER -

References

top
  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, (2002) 
  2. Bai, Y.Q., Ghami, M. El, Roos, C., 10.1137/S1052623403423114, SIAM J. Optim., 15, 2004, 101-128, (2004) MR2112978DOI10.1137/S1052623403423114
  3. Bouaafia, M., Benterki, D., Adnan, Y., 10.1051/ro/2015056, RAIRO-Oper. Res., 50, 2016, 935-949, (2016) MR3570540DOI10.1051/ro/2015056
  4. Bouaafia, M., Benterki, D., Adnan, Y., 10.1007/s11590-017-1170-5, Optim. Lett., 12, 2018, 1079-1097, (2018) MR3819677DOI10.1007/s11590-017-1170-5
  5. Ghami, M. El, New Primal-Dual Interior-Point Methods Based on Kernel Functions, 2005, TU Delft, The Netherlands, PhD Thesis. (2005) 
  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, (2008) MR2408056
  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, (1984) MR0779900
  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, (1989) MR0982720
  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, (2001) MR1860114
  10. Peng, J., Roos, C., Terlaky, T., 10.1016/S0377-2217(02)00275-8, European Journal of Operational Research, 143, 2002, 234-256, (2002) MR1934033DOI10.1016/S0377-2217(02)00275-8
  11. Peng, J., Roos, C., Terlaky, T., Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms, 2002, Princeton University Press, Princeton, (2002) MR1938497
  12. Roos, C., Terlaky, T., Vial, J.P., Theory and Algorithms for Linear Optimization, An Interior Point Approach, 1997, Wiley, Chichester, (1997) MR1450094
  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, (1986) MR0903521
  14. Ye, Y., Interior Point Algorithms, Theory and Analysis, 1997, Wiley, Chichester, (1997) MR1481160

NotesEmbed ?

top

You must be logged in to post comments.