Geodesic
Complexity analysis of a weighted-full-Newton step interior-point algorithm for P * (κ)-LCP
Achache, Mohamed1
1 Laboratoire de Mathématiques Fondamentales et Numériques. Université Ferhat Abbas, Sétif 1, 19000 Sétif, Algérie.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 131-143

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

In this paper, a weighted-path-following interior point algorithm for P * (κ)-linear complementarity problems (P * (κ)-LCP) is presented. The algorithm uses at each weighted interior point iteration only feasible full-Newton steps and the strategy of the central-path for getting a solution for P * (κ)-LCP. We prove that the proposed algorithm has quadratically convergent with polynomial time. The complexity bound, namely, O((1+κ)nlogn ϵ) of the algorithm is obtained. Few numerical tests are reported to show the efficiency of the algorithm.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015020
Classification : 90C33, 90C51, 11Y16
Keywords: Linear complementarity problems, P∗(κ)-matrix, weighted-path-following, interior-point methods, polynomial complexity

Achache, Mohamed 1

1 Laboratoire de Mathématiques Fondamentales et Numériques. Université Ferhat Abbas, Sétif 1, 19000 Sétif, Algérie. 
@article{RO_2016__50_1_131_0,
     author = {Achache, Mohamed},
     title = {Complexity analysis of a {weighted-full-Newton} step interior-point algorithm for $P_{\ast{}}(\kappa{})${-LCP}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {131--143},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ro/2015020},
     zbl = {1333.90132},
     mrnumber = {3460667},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2015020/}
}
TY  - JOUR
AU  - Achache, Mohamed
TI  - Complexity analysis of a weighted-full-Newton step interior-point algorithm for $P_{\ast{}}(\kappa{})$-LCP
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 131
EP  - 143
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2015020/
DO  - 10.1051/ro/2015020
LA  - en
ID  - RO_2016__50_1_131_0
ER  - 
%0 Journal Article
%A Achache, Mohamed
%T Complexity analysis of a weighted-full-Newton step interior-point algorithm for $P_{\ast{}}(\kappa{})$-LCP
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 131-143
%V 50
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2015020/
%R 10.1051/ro/2015020
%G en
%F RO_2016__50_1_131_0
Achache, Mohamed. Complexity analysis of a weighted-full-Newton step interior-point algorithm for $P_{\ast{}}(\kappa{})$-LCP. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 131-143. doi: 10.1051/ro/2015020

Cité par Sources :