Extension of primal-dual interior point method based on a kernel function for linear fractional problem
DOI:
https://doi.org/10.33993/jnaat522-1349Keywords:
linear optimization, recurrent sequence, kernel function, interior point methods, complexity boundAbstract
Our aim in this work is to extend the primal-dual interior point method based on a kernel function for linear fractional problem. We apply the techniques of kernel function-based interior point methods to solve a standard linear fractional program. By relying on the method of Charnes and Cooper [3], we transform the standard linear fractional problem into a linear program. This transformation will allow us to define the associated linear program and solve it efficiently using an appropriate kernel function. To show the efficiency of our approach, we apply our algorithm on the standard linear fractional programming found in numerical tests in the paper of A. Bennani et al. [4], we introduce the linear programming associated with this problem. We give three interior point conditions on this example, which depend on the dimension of the problem. We give the optimal solution for each linear program and each linear fractional program. We also obtain, using the new algorithm, the optimal solutions for the previous two problems. Moreover, some numerical results are illustrated to show the effectiveness of the method.
Downloads
References
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 (1), 101–128(2004). https://doi.org/10.1137/S1052623403423114 DOI: https://doi.org/10.1137/S1052623403423114
Y. Q. Bai, C. Roos, A primal-dual interior point method based on a new kernel function with linear growth rate, in: Proceedings of the 9th Australian Optimization Day, Perth, Australia,(2002)
A. Bennani, D. Benterki, H. Grar, adaptive projection methods for linear fractional programming, RAIRO Oper. Res.55, 2383–2392(2021) https://doi.org/10.1051/ro/2020091 DOI: https://doi.org/10.1051/ro/2020091
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) https://doi.org/10.1007/s10957-016-0895-0 DOI: https://doi.org/10.1007/s10957-016-0895-0
M. Bouafia, D. Benterki, A. Yassine, An efficient parameterized logarithmic kernel function for linear optimization, Optim. letters. 12(5), 1079–1097 (2018) https://doi.org/10.1007/s11590-017-1170-5 DOI: https://doi.org/10.1007/s11590-017-1170-5
M. Bouafia, A. Yassine, An efficient twice parameterized trigonometric kernel function for linear optimization, Optim. and Eng. 21, 651–672(2020) https://doi.org/10.1007/s11081-019-09467-w DOI: https://doi.org/10.1007/s11081-019-09467-w
M. Bouafia, A. Yassine, Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient Bi-parameterized kernel function with a trigonometric barrier term, RAIRO-Oper. Res. f ̄ 56, 731–750 (2022) https://doi.org/10.1051/ro/2022032 DOI: https://doi.org/10.1051/ro/2022032
A. Charnes, W. W. Cooper, Programming with Linear Fractional Functionals, Naval. Res. Logis. Quart. 9 (3–4), 181–186 (1962) https://doi.org/10.1002/nav.3800090303 DOI: https://doi.org/10.1002/nav.3800090303
M. El Ghami, New primal-dual interior-point methods based on kernel functions, PhD Thesis, TU Delft, The Netherlands (2005)
N. K. Karmarkar, A new polynomial-time algorithm for linear programming. Proceedings of the 16th Annual ACM Symposium on Theory of Computing. 4, 373–395 (1984) https://doi.org/10.1007/BF02579150 DOI: https://doi.org/10.1145/800057.808695
A. O. Odior, Mathematics for Science and Engineering Students. Vol.1, 3rd. Edition, Ambik Press, Benin City, Nigeria, (2003)
J. Peng, C. Roos, T. Terlaky, Self-Regularity: A New Paradigm for primal-dual interior point algorithms, Princeton University Press, Princeton. NJ (2002)
C. Roos, T. Terlaky, J. Ph. Vial, Theory and algorithms for linear optimization, an interior point approach, John Wiley & Sons, Chichester. UK (1997)
S. F. Tantawy, A New Method for Solving Linear Fractional Programming Problems, Australian Journal of Basic and Applied Sciences, 1 (2), 105–108 (2007)
I. J. Lustig, A practical approach to Karmarkar’s algorithm. Technical report sol 85-5 System optimization laboratory; Department of Operations Research Stanford. University of Stanford, CA, (1985)
Y. Ye, Interior point algorithms, Theory and analysis. John-Wiley. Sons, Chichester, UK (1997) DOI: https://doi.org/10.1002/9781118032701
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 mousaab Bouafia, adnan yassine
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
