Geodesic
Complexity analysis of interior point methods for linear programming based on a parameterized kernel function
Bouafia, Mousaab1, 2  ; Benterki, Djamel3  ; Yassine, Adnan2 
1 LabCAV, Laboratory of Advanced Control, University of 8 May 1945 Guelma. BP 401, 24000 Guelma, Algeria.
2 Normandie Univ, LMAH – ULH, FR CNRS 3335, 25 rue Philippe Lebon, 76600 Le Havre, France.
3 L.M.F.N, Laboratory of Fundamental and Numerical Mathematics, University Setif 1, 19000 Setif, Algeria.
RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 935-949

Voir la notice de l'article provenant de la source Numdam

Kernel function plays an important role in defining new search directions for primal-dual interior point algorithm for solving linear optimization problems. This problem has attracted the attention of many researchers for some years. The goal of their works is to find kernel functions that improve algorithmic complexity of this problem. In this paper, we introduce a real parameter p>0 to generalize the kernel function (5) given by Bai et al. in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101–128.], and give the corresponding primal-dual interior point methods for linear optimization. This parameterized kernel function yields the similar complexity bound given in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101–128.] for both large-update and small-update methods.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015056
Classification : 90C05, 90C31, 90C51
Keywords: Linear optimization, Kernel function, interior point methods, complexity bound

Bouafia, Mousaab 1, 2 ; Benterki, Djamel 3 ; Yassine, Adnan 2

1 LabCAV, Laboratory of Advanced Control, University of 8 May 1945 Guelma. BP 401, 24000 Guelma, Algeria.
2 Normandie Univ, LMAH – ULH, FR CNRS 3335, 25 rue Philippe Lebon, 76600 Le Havre, France.
3 L.M.F.N, Laboratory of Fundamental and Numerical Mathematics, University Setif 1, 19000 Setif, Algeria. 
@article{RO_2016__50_4-5_935_0,
     author = {Bouafia, Mousaab and Benterki, Djamel and Yassine, Adnan},
     title = {Complexity analysis of interior point methods for linear programming based on a parameterized kernel function},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {935--949},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4-5},
     year = {2016},
     doi = {10.1051/ro/2015056},
     mrnumber = {3570540},
     zbl = {1385.90017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2015056/}
}
TY  - JOUR
AU  - Bouafia, Mousaab
AU  - Benterki, Djamel
AU  - Yassine, Adnan
TI  - Complexity analysis of interior point methods for linear programming based on a parameterized kernel function
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 935
EP  - 949
VL  - 50
IS  - 4-5
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2015056/
DO  - 10.1051/ro/2015056
LA  - en
ID  - RO_2016__50_4-5_935_0
ER  - 
%0 Journal Article
%A Bouafia, Mousaab
%A Benterki, Djamel
%A Yassine, Adnan
%T Complexity analysis of interior point methods for linear programming based on a parameterized kernel function
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 935-949
%V 50
%N 4-5
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2015056/
%R 10.1051/ro/2015056
%G en
%F RO_2016__50_4-5_935_0
Bouafia, Mousaab; Benterki, Djamel; Yassine, Adnan. Complexity analysis of interior point methods for linear programming based on a parameterized kernel function. RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 935-949. doi: 10.1051/ro/2015056

Cité par Sources :