Geodesic
Primal-dual entropy-based interior-point algorithms for linear optimization
Karimi, Mehdi1 ; Luo, Shen2 ; Tunçel, Levent1 
1 Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
2 Toronto, Ontario, Canada.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 2, pp. 299-328

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

We propose a family of search directions based on primal-dual entropy in the context of interior-point methods for linear optimization. We show that by using entropy-based search directions in the predictor step of a predictor-corrector algorithm together with a homogeneous self-dual embedding, we can achieve the current best iteration complexity bound for linear optimization. Then, we focus on some wide neighborhood algorithms and show that in our family of entropy-based search directions, we can find the best search direction and step size combination by performing a plane search at each iteration. For this purpose, we propose a heuristic plane search algorithm as well as an exact one. Finally, we perform computational experiments to study the performance of entropy-based search directions in wide neighborhoods of the central path, with and without utilizing the plane search algorithms.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016020
Classification : 90C05, 90C51, 41A46, 94A17
Keywords: Interior-point methods, primal-dual entropy, central path, homogeneous and self-dual embedding, search direction

Karimi, Mehdi 1 ; Luo, Shen 2 ; Tunçel, Levent 1

1 Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
2 Toronto, Ontario, Canada. 
@article{RO_2017__51_2_299_0,
     author = {Karimi, Mehdi and Luo, Shen and Tun\c{c}el, Levent},
     title = {Primal-dual entropy-based interior-point algorithms for linear optimization},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {299--328},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {2},
     year = {2017},
     doi = {10.1051/ro/2016020},
     mrnumber = {3619706},
     zbl = {1365.90166},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2016020/}
}
TY  - JOUR
AU  - Karimi, Mehdi
AU  - Luo, Shen
AU  - Tunçel, Levent
TI  - Primal-dual entropy-based interior-point algorithms for linear optimization
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 299
EP  - 328
VL  - 51
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2016020/
DO  - 10.1051/ro/2016020
LA  - en
ID  - RO_2017__51_2_299_0
ER  - 
%0 Journal Article
%A Karimi, Mehdi
%A Luo, Shen
%A Tunçel, Levent
%T Primal-dual entropy-based interior-point algorithms for linear optimization
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 299-328
%V 51
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2016020/
%R 10.1051/ro/2016020
%G en
%F RO_2017__51_2_299_0
Karimi, Mehdi; Luo, Shen; Tunçel, Levent. Primal-dual entropy-based interior-point algorithms for linear optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 2, pp. 299-328. doi: 10.1051/ro/2016020

Cité par Sources :