Purification procedure for linear monotone complementarity problems

Abderrahim Kadiri; Adnan Yassine

RAIRO - Operations Research (2010)

  • Volume: 38, Issue: 1, page 63-83
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Kadiri, Abderrahim, and Yassine, Adnan. "Une procédure de purification pour les problèmes de complémentarité linéaire, monotones ." RAIRO - Operations Research 38.1 (2010): 63-83. <http://eudml.org/doc/105303>.

@article{Kadiri2010,
abstract = { 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. },
author = {Kadiri, Abderrahim, Yassine, Adnan},
journal = {RAIRO - Operations Research},
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.},
language = {fre},
month = {3},
number = {1},
pages = {63-83},
publisher = {EDP Sciences},
title = {Une procédure de purification pour les problèmes de complémentarité linéaire, monotones },
url = {http://eudml.org/doc/105303},
volume = {38},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 38
IS - 1
SP - 63
EP - 83
AB - 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.
LA - fre
KW - 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.
UR - http://eudml.org/doc/105303
ER -

References

top
  1. J.F. Bonnans, J.C. Gilbert, C. Lemarechal and C. Sagastizabal, Optimisation Numérique. Aspects théoriques et pratiques. Springer-Verlag (1997).  
  2. J.F. Bonnans and C.C. Gonzaga, Convergence of interior point algorithms for the monotone linear complementarity problem. Math. Oper. Res.21 (1996) 1-25.  Zbl0846.90109
  3. R.W. Cottle, J.S. Pang and V. Venkateswaran, Sufficient matrices and the linear complementarity problem. Linear AlgebraAppl.114/115 (1989) 231-249.  Zbl0674.90092
  4. F. Facchinei, A. Fischer and C. Kanzow, On the identification of zero variables in a interior-point framework. SIAM J. Optim.10 (2000) 1058-1078.  Zbl0999.90044
  5. C.C. Gonzaga, Path-following methods for linear programming. SIAM Rev.34 (1992) 167-224.  Zbl0763.90063
  6. T. Illes, J. Peng, C. Roos and T. Terlaky, A strongly polynomial rounding procedure yielding a maximally complementary solution for P*(k) linear complementarity problems. SIAM J. Optim.11 (2000) 320-340.  Zbl1010.90082
  7. J. Ji and A. Potra, 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.  Zbl0868.90121
  8. J. Ji, A. Potra and S.Huang, Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence. JOTA85 (1995) 187-199.  Zbl0824.90129
  9. A. Kadiri, 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. C.T. Kelley, Iterative methods for linear and nonlinear equations. Frontiers Appl. Math.16 (1995).  Zbl0832.65046
  11. M. Kojima, S. Mizuno and A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems. Math. Program.44 (1989) 1-26.  Zbl0676.90087
  12. M. Kojima, Y. Kurita and S. Mizuno, Large-step interior point algorithmsfor linear complementarity problems. SIAM J. Optim.3 (1993) 398-412.  Zbl0781.90085
  13. K. Kortanek and J. Zhu, New purification algorithms for linear programming. Naval Res. Logist35 (1988) 571-583.  Zbl0685.90070
  14. K. Mcshane, Superlineary convergent O ( n L ) -iteration interior-point algorithms for LP and the monotone LCP. SIAM J. Optim.4 (1994) 247-261.  Zbl0822.90102
  15. R. Monteiro and I. Adler, Interior path-following primal-dual algorithms, part II: Convex quadratic programming. Math. Program.44 (1989) 43-66.  Zbl0676.90039
  16. R. Monteiro and S. Wright, Local convergence of interior-point algorithms for degenerate monotone LCP. Comput. Optim. Appl.3 (1994) 131-155.  Zbl0801.90110
  17. C.R. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall. Englewood Cliffs, New Jersey (1982).  Zbl0503.90060
  18. F.A. Potra and R. Sheng, A superlineary convergent infeasible-interior-point algorithm for degenerate LCP. J. Optim. Theory Appl. 97 (1998) 249-269.  Zbl0907.90261
  19. Y. Ye, On the finite convergence of interior point algorithms for linear programming. Math. Program.57 (1992) 325-335.  Zbl0794.90036
  20. Y. Ye, Interior Point Algorithms: Theory and Analysis. John Wiley, New York (1997).  Zbl0943.90070
  21. Y. Ye and K.M. Anstreicher, On quadratic and O ( n L ) convergence of a predictor-corrector algorithm for LCP. Math. Program.62 (1993) 537-551.  Zbl0799.90111

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.