Groupe d’études et de recherche en analyse des décisions

Convergence locale des méthodes primales-duales en programmation non linéaire

Paul Armand Université de Limoges, France

Nous présentons une propriété de convergence locale des méthodes primales-duales pour résoudre un problème d'optimisation non linéaire avec contraintes. Nous considérons un algorithme primal-dual standard dans lequel les conditions de complémentarité du système d'optimalité initial sont perturbées par l'introduction d'un paramètre barrière. Ce paramètre est progressivement ramené à la valeur nulle au cours des itérations. L'algorithme consiste à linéariser le système perturbé, puis à appliquer une recherche linéaire pour maintenir leur stricte réalisabilité par rapport aux contraintes d'inégalité. L'analyse de convergence est effectuée pour une suite arbitraire du paramètre barrière qui tend vers zéro, non nécessairement décroissante. Sous des hypothèses standard, nous montrons en premier que si le premier itéré est dans le voisinage de convergence de la méthode de Newton appliquée au système initial, alors la suite des itérés converge vers la solution. De plus, si on suppose que la vitesse de convergence du paramètre barrière est au plus superlinéaire, alors le pas unité est asymptotiquement accepté et la suite des itérés est asymptotiquement tangente au chemin central. Ce résultat montre en particulier que la vitesse de convergence des itérés est la même que celle du paramètre barrière. Nous donnons un exemple qui montre que cette propriété peut être fausse lorsque le paramètre barrière tend quadratiquement vers zéro. Nous montrons enfin comment cette propriété de convergence peut être utilisée pour définir une nouvelle technique de globalisation des méthodes primales-duales. Quelques tests numériques sont présentés.