Geodesic
Theoretical and numerical result for linear optimization problem based on a new kernel function
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 12 (2019) no. 2, pp. 160-172.

Voir la notice de l'article provenant de la source Math-Net.Ru

The propose of this paper is to improve the complexity results of primal-dual interior-point methods for linear optimization (LO) problem. We define a new proximity function for (LO) by a new kernel function wich is a combination of the classic kernel function and a barrier term. We present various proprieties of this new kernel function. Futhermore, we formilate an algorithm for a large-update primal-dual interior-point method (IPM) for (LO). It is shown that the iteration bound for large-update and smal-update primal-dual interior points methods based on this function is a good as the currently best know iteration bounds for these type of methods. This result decreases the gap between the practical behaviour of the large-update algorithms and their theoretical performance, which is an open problem.The primal-dual algorithm is implemented with different choices of the step size. Numerical results show that the algorithm with practical and dynamic step sizes is more efficient than that with fixed (theoretical) step size.
Keywords: kernel function, interior point algorithms, linear optimization, complexity bound, primal-dual methods. 
@article{JSFU_2019_12_2_a2,
     author = {Louiza Derbal and Zakia Kebbiche},
     title = {Theoretical and numerical result for linear optimization problem based on a new kernel function},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {160--172},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2019_12_2_a2/}
}
TY  - JOUR
AU  - Louiza Derbal
AU  - Zakia Kebbiche
TI  - Theoretical and numerical result for linear optimization problem based on a new kernel function
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2019
SP  - 160
EP  - 172
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2019_12_2_a2/
LA  - en
ID  - JSFU_2019_12_2_a2
ER  - 
%0 Journal Article
%A Louiza Derbal
%A Zakia Kebbiche
%T Theoretical and numerical result for linear optimization problem based on a new kernel function
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2019
%P 160-172
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2019_12_2_a2/
%G en
%F JSFU_2019_12_2_a2
Louiza Derbal; Zakia Kebbiche. Theoretical and numerical result for linear optimization problem based on a new kernel function. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 12 (2019) no. 2, pp. 160-172. http://geodesic.mathdoc.fr/item/JSFU_2019_12_2_a2/

[1] M. Achache, “A new parameterized kernel function for LO yielding the best known iteration bound for a large-update interior point algorithm”, Afrika Matematika, 27:3–4 (2016), 591–601 | DOI | MR | Zbl

[2] Y.Q. Bai, M. El Ghami, C. Roos, “A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization”, SIAM Journal on Optimization, 15:1 (2004), 101–128 | DOI | MR | Zbl

[3] D. Den Hertog, “Interior point approach to linear, quadratic, and convex programming”, Mathematics and its Applications, 277, Kluwer Academic Publishers, Dordrecht, 1994 | MR | Zbl

[4] M. Bouafia, D. Benterki, A. Yassine, “An efficient parameterized logarithmic kernel function for linear optimization”, Optimization Letters, 2018 | MR | Zbl

[5] N.K. Karmarkar, “A new polynomial-time algorithm for linear programming”, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 1984, 302–311 | MR

[6] A. Keraghel, Etude adaptative et comparative des principales variantes dans l'algorithme de karmarkar, Thèse de Doctorat, Université de Joseph Fourier Grenoble I, France, 1989

[7] B. Kheirfam, M. Haghighi, “A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function”, Journal of Mathematical Programming and Operations Research, 65:4 (2016), 841–857 | MR | Zbl

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

[9] Z.G. Qian, Y.Q. Bay, “Primal-dual Interior-Point Algorithms with Dynamic Step SizeBased on kernel functions for linear Programming”, Journal of Shanghai University, 9:5 (2005), 391–396 | DOI | MR | Zbl

[10] C. Roos, T. Terlaky, J.-Ph.Vial, Theory and Algorithms for Linear Optimization, An Interior-Point Approach, John Wiley Sons, Chichester, UK, 1997 | MR

[11] G. Sonnevend, “An “analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming”, System Modelling and Optimization, Proceedings of 12th IFIP-Conference (Budapest, Hungary, 1985), Lecture Notes in Control and Inform. Sci., 84, eds. Prekopa A, J., Szelezsan B., Springer, Berlin, 1986, 866–876 | DOI | MR

[12] R.J. Vanderbei, Linear Programming, Foundations and Extensions, International Series in Operations Research and Management Science, 7, 2nd ed. | MR

[13] Y. Ye, Interior Point Algorithms, Theory and Analysis, John Wiley and Sons, Chichester, UK, 1997 | MR | Zbl