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.
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.
Keywords: 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
@article{RO_2004__38_1_63_0, author = {Kadiri, Abderrahim and Yassine, Adnan}, title = {Une proc\'edure de purification pour les probl\`emes de compl\'ementarit\'e lin\'eaire, monotones}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {63--83}, publisher = {EDP-Sciences}, volume = {38}, number = {1}, year = {2004}, doi = {10.1051/ro:2004012}, mrnumber = {2083972}, zbl = {1092.90051}, language = {fr}, url = {http://archive.numdam.org/articles/10.1051/ro:2004012/} }
TY - JOUR AU - Kadiri, Abderrahim AU - Yassine, Adnan TI - Une procédure de purification pour les problèmes de complémentarité linéaire, monotones JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2004 SP - 63 EP - 83 VL - 38 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2004012/ DO - 10.1051/ro:2004012 LA - fr ID - RO_2004__38_1_63_0 ER -
%0 Journal Article %A Kadiri, Abderrahim %A Yassine, Adnan %T Une procédure de purification pour les problèmes de complémentarité linéaire, monotones %J RAIRO - Operations Research - Recherche Opérationnelle %D 2004 %P 63-83 %V 38 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2004012/ %R 10.1051/ro:2004012 %G fr %F RO_2004__38_1_63_0
Kadiri, Abderrahim; Yassine, Adnan. Une procédure de purification pour les problèmes de complémentarité linéaire, monotones. RAIRO - Operations Research - Recherche Opérationnelle, Volume 38 (2004) no. 1, pp. 63-83. doi : 10.1051/ro:2004012. http://archive.numdam.org/articles/10.1051/ro:2004012/
[1] Optimisation Numérique. Aspects théoriques et pratiques. Springer-Verlag (1997). | MR | Zbl
, , and ,[2] Convergence of interior point algorithms for the monotone linear complementarity problem. Math. Oper. Res. 21 (1996) 1-25. | MR | Zbl
and ,[3] Sufficient matrices and the linear complementarity problem. Linear Algebra Appl. 114/115 (1989) 231-249. | MR | Zbl
, and ,[4] On the identification of zero variables in a interior-point framework. SIAM J. Optim. 10 (2000) 1058-1078. | MR | Zbl
, and ,[5] Path-following methods for linear programming. SIAM Rev. 34 (1992) 167-224. | MR | Zbl
,[6] A strongly polynomial rounding procedure yielding a maximally complementary solution for linear complementarity problems. SIAM J. Optim. 11 (2000) 320-340. | MR | Zbl
, , and ,[7] Tapia indicators and finite termination of infeasible-interior-point methods for degenerate LCP, edited by J. Renegar, M. Shub and S. Smale. AMS, Providence, RI. Math. Numer. Anal., Lect. Appl. Math. 32 (1996) 443-454. | MR | Zbl
and ,[8] Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence. JOTA 85 (1995) 187-199. | MR | Zbl
, and ,[9] Analyse numérique des méthodes de points intérieurs pour les problèmes de complémentarité linéaire et la programmation quadratique convexe. Thèse de Doctorat, INSA de Rouen (2001).
,[10] Iterative methods for linear and nonlinear equations. Frontiers Appl. Math. 16 (1995). | MR | Zbl
,[11] A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44 (1989) 1-26. | MR | Zbl
, and ,[12] Large-step interior point algorithmsfor linear complementarity problems. SIAM J. Optim. 3 (1993) 398-412. | MR | Zbl
, and ,[13] New purification algorithms for linear programming. Naval Res. Logist 35 (1988) 571-583. | MR | Zbl
and ,[14] Superlineary convergent -iteration interior-point algorithms for LP and the monotone LCP. SIAM J. Optim. 4 (1994) 247-261. | MR | Zbl
,[15] Interior path-following primal-dual algorithms, part II: Convex quadratic programming. Math. Program. 44 (1989) 43-66. | MR | Zbl
and ,[16] Local convergence of interior-point algorithms for degenerate monotone LCP. Comput. Optim. Appl. 3 (1994) 131-155. | MR | Zbl
and ,[17] Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall. Englewood Cliffs, New Jersey (1982). | MR | Zbl
and ,[18] A superlineary convergent infeasible-interior-point algorithm for degenerate LCP. J. Optim. Theory Appl. 97 (1998) 249-269. | MR | Zbl
and ,[19] On the finite convergence of interior point algorithms for linear programming. Math. Program. 57 (1992) 325-335. | MR | Zbl
,[20] Interior Point Algorithms: Theory and Analysis. John Wiley, New York (1997). | MR | Zbl
,[21] On quadratic and convergence of a predictor-corrector algorithm for LCP. Math. Program. 62 (1993) 537-551. | MR | Zbl
and ,Cited by Sources: