Les méthodes de projection sur des espaces de Krylov ont été employées avec grand succès pour diverses tâches en calcul scientifique, par exemple la résolution de grands systèmes d’équations linéaires, le calcul approché de valeurs propres, ou encore le calcul approché des fonctions de matrices fois un vecteur. L’objectif majeur de cette thèse est d’étudier et d’expliquer la convergence superlinéaire des méthodes de Krylov. La plupart des résultats existants sont asymptotiques avec passage à la racine n-ième et considèrent des suites de matrices. Dans un premier temps, nous généralisons une formule de Ipsen et al. concernant la convergence superlinéaire des méthodes MR valable pour des disques, à l’aide des opérateurs de Hankel et de la théorie AAK. Notre analyse permet aussi d’obtenir des bornes supérieures pour des ensembles convexes en utilisant la transformée de Faber. Ensuite nous énonçons notre principal résultat qui est un théorème d’optimalité en théorie du potentiel logarithmique. Nous montrons, à l’aide d’une nouvelle technique de discrétisation d’un potentiel, que l’inégalité de Bernstein-Walsh à poids sur un intervalle réel est optimale, à un facteur universel près, dans le cas où le champs extérieur est un potentiel d’une mesure à support réel à gauche de l’intervalle, ce qui inclut le cas des poids polynômiaux. Via un lien avec un problème sous contrainte, l’inégalité précédente s’applique à l’analyse de la convergence des méthodes de Krylov, et permet de prédire analytiquement un taux de convergence superlinéaire de la méthode du gradient conjugué et des approximations de Rayleigh-Ritz pour des fonctions de Markov, à chaque étape et pour une seule matrice. / Projection methods on Krylov spaces were used with great success for various tasks in scientific computing, for example the resolution of large systems of linear equations, the approximate computation of eigenvalues, or the approximate computation of matrix functions times a vector. The main goal in this thesis is to study and explain superlinear convergence of Krylov methods. Most of the existing formulas provide asymptotic results for the n-th root considering an increasing sequence of matrices. Firstly, we generalize a formula of Ipsen et al. concerning superlinear convergence of MR methods valid for disks using Hankel operators and AAK theory, our analysis also allows to obtain upper bounds for convex sets using the Faber transform. Then we state our main theorem which is a sharpness result in logarithmic potential theory using a new technique of discretization of a logarithmic potential. We prove that the weighted Bernstein-Walsh inequality on a real interval is sharp up to some universal constant, when the external field is given by a potential of a real measure supported at the left of the interval. As a special case this result includes the case of weights given by polynomials. Via a link with a constrained extremal problem our inequality applies to the analysis of the convergence of Krylov methods, and allows us to predict analytically the superlinear convergence of the conjugate gradient method and of the error for Rayleigh-Ritz approximations for Markov functions. Our results apply to a simple matrix, without taking the limit and without n-th root.

Cette thèse s'intéresse à des méthodes de points intérieurs et de quasi-Newton en optimisation non linéaire et à leurs mises en oeuvre. On présente le code NOPTIQ utilisant les formules de BFGS à mémoire limitée pour résoudre des problèmes de grande taille. L'originalité de cette approche est l'emploi de ces formules dans le cadre des méthodes de points intérieurs. L'espace mémoire et le coût en opérations du calcul d'une itération sont alors faibles. Le code NOPTIQ est robuste et a des performances comparables avec les codes de références l-BFGS-B et LANCELOT. On présente aussi un algorithme non réalisable utilisant les méthodes précédentes pour résoudre un problème non linéaire avec contraintes d'inégalité et contraintes d'égalité linéaire. L'idée est de pénaliser le problème à l'aide de variables de décalage et d'une variante de la méthode big-M. La convergence q-superlinéaire des itérés internes et la convergence globale des itérés externes sont démontrées.

Dans cette thèse, nous nous étudions des algorithmes d’optimisation non linéaire. D’une part nous proposons des techniques de détection rapide de la non-réalisabilité d’un problème à résoudre. D’autre part, nous analysons le comportement local des algorithmes pour la résolution de problèmes singuliers. Dans la première partie, nous présentons une modification d’un algorithme de lagrangien augmenté pour l’optimisation avec contraintes d’égalité. La convergence quadratique du nouvel algorithme dans le cas non-réalisable est démontrée théoriquement et numériquement. La seconde partie est dédiée à l’extension du résultat précédent aux problèmes d’optimisation non linéaire généraux avec contraintes d’égalité et d’inégalité. Nous proposons une modification d’un algorithme de pénalisation mixte basé sur un lagrangien augmenté et une barrière logarithmique. Les résultats théoriques de l’analyse de convergence et quelques tests numériques montrent l’avantage du nouvel algorithme dans la détection de la non-réalisabilité. La troisième partie est consacrée à étudier le comportement local d’un algorithme primal-dual de points intérieurs pour l’optimisation sous contraintes de borne. L’analyse locale est effectuée sans l’hypothèse classique des conditions suffisantes d’optimalité de second ordre. Celle-ci est remplacée par une hypothèse plus faible basée sur la notion de borne d’erreur locale. Nous proposons une technique de régularisation de la jacobienne du système d’optimalité à résoudre. Nous démontrons ensuite des propriétés de bornitude de l’inverse de ces matrices régularisées, ce qui nous permet de montrer la convergence superlinéaire de l’algorithme. La dernière partie est consacrée à l’analyse de convergence locale de l’algorithme primal-dual qui est utilisé dans les deux premières parties de la thèse. En pratique, il a été observé que cet algorithme converge rapidement même dans le cas où les contraintes ne vérifient l’hypothèse de qualification de Mangasarian-Fromovitz. Nous démontrons la convergence superlinéaire et quadratique de cet algorithme, sans hypothèse de qualification des contraintes. / This thesis is devoted to the study of numerical algorithms for nonlinear optimization. On the one hand, we propose new strategies for the rapid infeasibility detection. On the other hand, we analyze the local behavior of primal-dual algorithms for the solution of singular problems. In the first part, we present a modification of an augmented Lagrangian algorithm for equality constrained optimization. The quadratic convergence of the new algorithm in the infeasible case is theoretically and numerically demonstrated. The second part is dedicated to extending the previous result to the solution of general nonlinear optimization problems with equality and inequality constraints. We propose a modification of a mixed logarithmic barrier-augmented Lagrangian algorithm. The theoretical convergence results and the numerical experiments show the advantage of the new algorithm for the infeasibility detection. In the third part, we study the local behavior of a primal-dual interior point algorithm for bound constrained optimization. The local analysis is done without the standard assumption of the second-order sufficient optimality conditions. These conditions are replaced by a weaker assumption based on a local error bound condition. We propose a regularization technique of the Jacobian matrix of the optimality system. We then demonstrate some boundedness properties of the inverse of these regularized matrices, which allow us to prove the superlinear convergence of our algorithm. The last part is devoted to the local convergence analysis of the primal-dual algorithm used in the first two parts of this thesis. In practice, it has been observed that this algorithm converges rapidly even in the case where the constraints do not satisfy the Mangasarian-Fromovitz constraint qualification. We demonstrate the superlinear and quadratic convergence of this algorithm without any assumption of constraint qualification.