21787 articles – 15600 Notices  [english version]

inria-00074242, version 1

Fast convergence of the simplified largest step path following algorithm

Clovis C. Gonzaga, J. Frederic Bonnans () 1

N° RR-2433 (1994)

Résumé : Each master iteration of a simplified Newton algorithm for solving a system of equations starts by computing the Jacobian matrix and then uses this matrix in the computation of $ p $ Newton steps: the first of these steps is exact, and the other are called ``simplified''. In this paper we apply this approach to a large step path following algorithm for monotone linear complementarity problems. The resulting method generates sequences of objective values (duality gaps) that converge to zero with Q-order $ p+1$ in the number of master iterations, and with a complexity of $ O(\sqrt n L) $ iterations.

  • 1 :  PROMATH (INRIA Rocquencourt)
  • INRIA
  • Domaine : Informatique/Autre
    Mathématiques/Optimisation et contrôle
  • Mots-clés : LINEAR COMPLEMENTARITY PROBLEM / PRIMAL-DUAL INTERIOR-POINT ALGORITHM / CONVERGENCE OF ALGORITHMS / SIMPLIFIED NEWTON METHOD
  • Référence interne : RR-2433
  • Commentaire : Projet PROMATH
 
  • inria-00074242, version 1
  • http://hal.inria.fr/inria-00074242
  • oai:hal.inria.fr:inria-00074242
  • Contributeur : Rapport De Recherche Inria <>
  • Soumis le : Mercredi 24 Mai 2006, 14:50:49
  • Dernière modification le : Lundi 14 Mai 2007, 12:35:11