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.
Accepté le :
DOI : 10.1051/ro/2016020
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
@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 :