Issue RAIRO Oper. Res. Volume 38, Number 1, January-March 2004 Page(s) 63 - 83 DOI 10.1051/ro:2004012

RAIRO Oper. Res. 38 (2004) 63-83
DOI: 10.1051/ro:2004012

Une procédure de purification pour les problèmes de complémentarité linéaire, monotones

Abderrahim Kadiri and Adnan Yassine

LMAH, Université du Havre, BP 540, 76058 Le Havre, France ; adnan.yassine@univ-lehavre.fr.
(Reçu le 2 september 2002.)

Abstract
In this paper, we propose a new purification method for monotone linear complementarity problems. This method associates to each iterate of the sequence, generated by an interior point method, one basis which is not necessarily feasible. We show that, under the strict complementarity and non-degeneracy hypoteses, the sequence of bases converges on a finite number of iterations to an optimal basis which gives the exact solution of the problem. The adopted process also serves to preconditioning the conjugate gradient algorithm when computing the Newton direction.

Résumé
Dans cet article, nous proposons une nouvelle méthode de purification pour les problèmes de complémentarité linéaire, monotones. Cette méthode associe à chaque itéré de la suite, générée par une méthode de points intérieurs, une base non nécessairement réalisable. Nous montrons que, sous les hypothèses de complémentarité stricte et de non dégénérescence, la suite des bases converge en un nombre fini d'itérations vers une base optimale qui donne une solution exacte du problème. Le procédé adopté sert également à préconditionner l'algorithme de gradient conjugué lors du calcul de la direction de Newton.

Mathematics Subject Classification. 65K05, 90C33, 90C51.

Key words: Problèmes de complémentarité linéaire, méthodes de points intérieurs, purification, solution exacte, convergence finie, gradient conjugué, préconditionnement, programmation quadratique convexe.


© EDP Sciences 2004

What is OpenURL?