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
• oai:hal.inria.fr:inria-00074242
• Contributeur :
• Soumis le : Mercredi 24 Mai 2006, 14:50:49
• Dernière modification le : Lundi 14 Mai 2007, 12:35:11