Geodesic
Generic primal-dual interior point methods based on a new kernel function
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 199-213

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

In this paper we present a generic primal-dual interior point methods (IPMs) for linear optimization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. The proposed kernel function does not satisfy all the conditions proposed in [2]. We show that the corresponding large-update algorithm improves the iteration complexity with a factor n 1 6 when compared with the method based on the use of the classical logarithmic barrier function. For small-update interior point methods the iteration bound is O(nlogn ϵ), which is currently the best-known bound for primal-dual IPMs.

DOI : 10.1051/ro:2008009
Classification : 90C05, 90C31
Keywords: linear optimization, primal-dual interior-point algorithm, large and small-update method 
@article{RO_2008__42_2_199_0,
     author = {Ghami, M. El and Roos, C.},
     title = {Generic primal-dual interior point methods based on a new kernel function},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {199--213},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ro:2008009},
     mrnumber = {2431399},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2008009/}
}
TY  - JOUR
AU  - Ghami, M. El
AU  - Roos, C.
TI  - Generic primal-dual interior point methods based on a new kernel function
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 199
EP  - 213
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2008009/
DO  - 10.1051/ro:2008009
LA  - en
ID  - RO_2008__42_2_199_0
ER  - 
%0 Journal Article
%A Ghami, M. El
%A Roos, C.
%T Generic primal-dual interior point methods based on a new kernel function
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 199-213
%V 42
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2008009/
%R 10.1051/ro:2008009
%G en
%F RO_2008__42_2_199_0
Ghami, M. El; Roos, C. Generic primal-dual interior point methods based on a new kernel function. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 199-213. doi: 10.1051/ro:2008009

Cité par Sources :