Ce travail se scinde principalement en deux grandes composantes ; l'une de type théorique et l'autre de type numérique. Dans la partie théorique, on se place dans le cadre de l'optimisation non linéaire avec contraintes. La globalisation d'un algorithme de points intérieurs par des régions de confiance est examinée et l'on détaille ses propriétés de convergence, étayées par des expérimentations numériques sur des problèmes de programmation quadratique. Sous des hypothèses du premier et second ordre, les propriétés de convergence locale, asymptotique, d'une classe d'algorithmes de points intérieurs, parmi laquelle l'algorithme précédent, sont étudiées et l'on montre que l'on peut obtenir une convergence sous-quadratique qui a lieu en composantes. Les résultats sont généralisés à un taux de convergence arbitrairement élevé, au prix de la résolution d'un nombre suffisamment élevé de systèmes de Newton pour chaque valeur du paramètre barrière. Ces résultats asymptotiques supposent que la condition de qualification des contraintes d'indépendance des gradients actifs est satisfaite. Il s'avère que la condition de qualification des contraintes peut être relachée en la condition de Mangasarian et Fromowitz, tout en conservant les propriétés de convergence importantes. Les techniques utilisées et les résultats de convergence asymptotique en les composantes sont enfin généralisés à la résolution de systèmes d'équations non linéaires de rang plein. Dans la composante numérique, on examine ensuite l'environnement CUTE et l'on décrit les nouvelles fonctionnalités et les apports de CUTEr.

Les nouvelles méthodes de points intérieurs jouent aujourd'hui un rôle de plus en plus important dans l'optimisation des systèmes de grande taille. Dans cette thèse nous étudions dans une première partie, du point de vue théorique et numérique, une extension d'un algorithme de points intérieurs pour la programmation quadratique convexe et non convexe. Celle-ci utilise l'idée de la région de confiance que l'on peut expliciter grâce à une transformation affine. Sous certaines hypothèses nous démontrons des résultats sur la convergence globale et sur la vitesse de convergence de l'algorithme. Nous donnons aussi une version pratique de cet algorithme, basée sur une généralisation de la méthode de Lanczos pour la résolution des systèmes linéaires indéfinis. Celle-ci donne dans la pratique des résultats très encourageants. Dans la seconde partie, nous étudions du point de vue théorique une extension d'un autre algorithme de points intérieurs pour l'optimisation non linéaire avec contraintes linéaires. Cette extension utilise l'idée de la réduction d'une fonction potentiel après une transformation affine de l'ensemble admissible. Des résultats sur la convergence globale et sur la complexité de l'algorithme sont donnés.

This volume contains the edited texts of the lectures presented at the Workshop on High Performance Algorithms and Software for Nonlinear Optimization held in Erice, Sicily, at the "G. Stampacchia" School of Mathematics of the "E. Majorana" Centre for Scientific Culture, June 30 - July 8, 2001. In the first year of the new century, the aim of the Workshop was to assess the past and to discuss the future of Nonlinear Optimization, and to highlight recent achieve ments and promising research trends in this field. An emphasis was requested on algorithmic and high performance software developments and on new computational experiences, as well as on theoretical advances. We believe that such goal was basically achieved. The Workshop was attended by 71 people from 22 countries. Although not all topics were covered, the presentations gave indeed a wide overview of the field, from different and complementary stand points. Besides the lectures, several formal and informal discussions took place. We wish to express our appreciation for the active contribution of all the participants in the meeting. The 18 papers included in this volume represent a significant selection of the most recent developments in nonlinear programming theory and practice. They show that there is plenty of exciting ideas, implementation issues and new applications which produce a very fast evolution in the field.

LES METHODES DE GRADIENTS. UN ALGORITHME DE POINTS REALISABLES POUR L'OPTIMISATION AVEC CONTRAINTES NON LINEAIRES. LES METRIQUES VARIABLES ET L'OPTIMISATION AVEC CONTRAINTES

Dans cette étude, nous nous intéressons au problème d'initialisation dans les méthodes de points intérieurs de types trajectoire centrale, en prenant comme référence les travaux de Y. Zhang pour la programmation linéaire (PL). Après avoir mis en oeuvre un algorithme pour la programmation linéaire (PL), nous proposons une extension pour la programmation quadratique convexe (PQC) puis pour la programmation semidéfinie (PSD).

Ce travail décrit NLPHOPDM, un nouvel algorithme pour l'optimisation convexe différentiable. Par rapport aux méthodes intérieures classiques, il raffine les correcteurs multiples de centralité et perturbe les contraintes d'admissibilité dans la méthode de Newton. Son efficacité est évaluée sur des problèmes économiques et d'ingéniérie où la minimisation d'une fonction sous contraintes (surplus, énergie potentielle) caractérise un équilibre. Concernant les conséquences du protocole de Kyoto sur le marché énergétique, qui sont modélisées par un problème non linéaire de plusieurs milliers de variables, NLPHOPDM calcule un équilibre entre 2 et 400 fois plus rapidement que les algorithmes de référence. Concernant la déformation d'un milieu continu élastique soumis à des forces externes, dont la discrétisation en éléments finis conduit à des problèmes avec plusieurs dizaines de milliers de contraintes quadratiques, NLPHOPDM trouve un design optimal en 2 à 15 fois moins d'itérations que les méthodes intérieures de référence pour les problèmes considérés.

Analyse: L'optimisation offre un cadre mathématique permettant d'interpréter et de résoudre un grand nombre de problèmes de gestion, d'économie, de mathématique et de physique.