Extension of primal-dual interior point method based on a kernel function for linear fractional problem

Authors

  • Mousaab Bouafia University of 8 May 1945 Guelma, Algeria & LMAH, FR-CNRS-3335, Le Havre, France https://orcid.org/0000-0002-8899-4630
  • Adnan Yassine Normandie University, UNIHAVRE, LMAH, FR-CNRS-3335, Le Havre, France

DOI:

https://doi.org/10.33993/jnaat522-1349

Keywords:

linear optimization, recurrent sequence, kernel function, interior point methods, complexity bound
Abstract views: 126

Abstract

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

Download data is not yet available.

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

Downloads

Published

2023-12-28

How to Cite

Bouafia, M., & Yassine, A. (2023). Extension of primal-dual interior point method based on a kernel function for linear fractional problem. J. Numer. Anal. Approx. Theory, 52(2), 162–171. https://doi.org/10.33993/jnaat522-1349

Issue

Section

Articles