Made available in DSpace on 2015-04-22T22:16:14Z (GMT). No. of bitstreams: 1 Andrea Freitas Fragata.pdf: 328937 bytes, checksum: eaf5f22018331e8d3fc583a6174a86b3 (MD5) Previous issue date: 2007-03-30 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Many problems in Physics, Engineering, Economics and other sciences are modeled by suitable nonlinear systems. In these models, we can use Newton s iterative method for approximating solutions, starting from an initial approximation which is assumed to be sufficiently good. The goal of this work is to give a proof that, under the assumptions of Smale s theorem, the method converges Qquadratically. The proof presented is based on some results proved by João Xavier e Orizon Ferreira, which improve previous results giving only the R-quadratic convergence of the method. / Muitos problemas de física, engenharia, ecomomia e outras ciências são modelados de maneira muito conveniente por sistemas não lineares. Nestes casos, podemos usar o método de Newton, que é um método iterativo, no sentido de garantir a convergência a uma solução, supondo que o ponto inicial usado como aproximação da mesma é suficientemente bom. O objetivo deste trabalho é dar uma demonstração, baseada nos resultados obtidos por João Xavier e Orizon Ferreira, que o Método de Newton sob as hipóteses do Teorema de Smale converge Q-quadraticamente e como conseqüência esses autores deduziram um erro estimado, o que configura um resultado novo, uma vez que, apenas a convergência R-quadrática foi obtida.

Les problèmes de complémentarité interviennent dans de nombreux domaines scientifiques : économie, mécanique des solides, mécanique des fluides. Ce n’est que récemment qu’ils ont commencé d’intéresser les chercheurs étudiant les écoulements et le transport en milieu poreux. Les problèmes de complémentarité sont un cas particulier des inéquations variationnelles. Dans cette thèse, on offre plusieurs contributions aux méthodes numériques pour résoudre les problèmes de complémentarité. Dans la première partie de cette thèse, on étudie les problèmes de complémentarité linéaires 0 6 x ⊥ (Mx+q) > 0 où, x l’inconnue est dans Rn et où les données sont q, un vecteur de Rn, et M, une matrice d’ordre n. L’existence et l’unicité de ce problème est obtenue quand la matrice M est une P-matrice. Une méthode très efficace pour résoudre les problèmes de complémentarité est la méthode de Newton-min, une extension de la méthode de Newton aux problèmes non lisses.Dans cette thèse on montre d’abord, en construisant deux familles de contre-exemples, que la méthode de Newton-min ne converge pas pour la classe des P-matrices, sauf si n= 1 ou 2. Ensuite on caractérise algorithmiquement la classe des P-matrices : c’est la classe des matrices qui sont telles que quel que, soit le vecteur q, l’algorithme de Newton-min ne fait pas de cycle de deux points. Enfin ces résultats de non-convergence nous ont conduit à construire une méthode de globalisation de l’algorithme de Newton-min dont nous avons démontré la convergence globale pour les P-matrices. Des résultats numériques montrent l’efficacité de cet algorithme et sa convergence polynomiale pour les cas considérés. Dans la deuxième partie de cette thèse, nous nous sommes intéressés à un exemple de problème de complémentarité non linéaire concernant les écoulements en milieu poreux. Il s’agit d’un écoulement liquide-gaz à deux composants eau-hydrogène que l’on rencontre dans le cadre de l’étude du stockage des déchets radioactifs en milieu géologique. Nous présentons un modèle mathématique utilisant des conditions de complémentarité non linéaires décrivant ces écoulements. D’une part, nous proposons une méthode de résolution et un solveur pour ce problème. D’autre part, nous présentons les résultats numériques que nous avons obtenus suite à la simulation des cas-tests proposés par l’ANDRA (Agence Nationale pour la gestion des Déchets Radioactifs) et le GNR MoMaS. En particulier, ces résultats montrent l’efficacité de l’algorithme proposé et sa convergence quadratique pour ces cas-tests / This manuscript deals with numerical methods for linear and nonlinear complementarity problems,and, more specifically, with solving gas phase appearance and disappearance modeled as a complementarity problem. In the first part of this manuscript, we focused on the plain Newton-min method to solve the linear complementarity problem (LCP for short) 0 6 x ⊥ (Mx+q) > 0 that can be viewed as a nonsmooth Newton algorithm without globalization technique to solve the system of piecewise linear equations min(x,Mx+q) = 0, which is equivalent to the LCP. When M is an M-matrix of order n, the algorithm was known to converge in at most n iterations. We show that this resultno longer holds when M is a P-matrix of order > 3. On the one hand, we offer counter-examplesshowing that the algorithm may cycle in those cases. P-matrices are interesting since they are thoseensuring the existence and uniqueness of the solution to the LCP for an arbitrary q. Incidentally,convergence occurs for a P-matrix of order 1 or 2. On the other hand, we provide a new algorithmic characterization of P-matricity : we show that a nondegenerate square real matrix M is a P-matrixif and only if, whatever is the real vector q, the Newton-min algorithm does not cycle between twopoints. In order to force the convergence of the Newton-min algorithm with P-matrices, we havederived a new method, which is robust, easy to describe, and simple to implement. It is globallyconvergent and the numerical results reported in this manuscript show that it outperforms a methodof Harker and Pang. In the second part of this manuscript, we consider the modeling of migration of hydrogen produced by the corrosion of the nuclear waste packages in an underground storage including the dissolution of hydrogen. It results in a set of nonlinear partial differential equations with nonlinear complementarity constraints. We show how to apply a robust and efficient solution strategy, the Newton-min method considered for LCP in the first part, to this geoscience problem and investigates its applicability and efficiency on this difficult problem. The practical interest of this solution technique is corroborated by numerical experiments from the Couplex Gas benchmark proposed by Andra and GNR MoMas. In particular, numerical results show that the Newton-min method is quadratically convergent for these problems

In this thesis we consider constrained systems of equations. The focus is on local Newton-type methods for the solution of constrained systems which converge locally quadratically under mild assumptions implying neither local uniqueness of solutions nor differentiability of the equation function at solutions. The first aim of this thesis is to improve existing local convergence results of the constrained Levenberg-Marquardt method. To this end, we describe a general Newton-type algorithm. Then we prove local quadratic convergence of this general algorithm under the same four assumptions which were recently used for the local convergence analysis of the LP-Newton method. Afterwards, we show that, besides the LP-Newton method, the constrained Levenberg-Marquardt method can be regarded as a special realization of the general Newton-type algorithm and therefore enjoys the same local convergence properties. Thus, local quadratic convergence of a nonsmooth constrained Levenberg-Marquardt method is proved without requiring conditions implying the local uniqueness of solutions. As already mentioned, we use four assumptions for the local convergence analysis of the general Newton-type algorithm. The second aim of this thesis is a detailed discussion of these convergence assumptions for the case that the equation function of the constrained system is piecewise continuously differentiable. Some of the convergence assumptions seem quite technical and difficult to check. Therefore, we look for sufficient conditions which are still mild but which seem to be more familiar. We will particularly prove that the whole set of the convergence assumptions holds if some set of local error bound conditions is satisfied and in addition the feasible set of the constrained system excludes those zeros of the selection functions which are not zeros of the equation function itself, at least in a sufficiently small neighborhood of some fixed solution. We apply our results to constrained systems arising from complementarity systems, i.e., systems of equations and inequalities which contain complementarity constraints. Our new conditions are discussed for a suitable reformulation of the complementarity system as constrained system of equations by means of the minimum function. In particular, it will turn out that the whole set of the convergence assumptions is actually implied by some set of local error bound conditions. In addition, we provide a new constant rank condition implying the whole set of the convergence assumptions. Particularly, we provide adapted formulations of our new conditions for special classes of complementarity systems. We consider Karush-Kuhn-Tucker (KKT) systems arising from optimization problems, variational inequalities, or generalized Nash equilibrium problems (GNEPs) and Fritz-John (FJ) systems arising from GNEPs. Thus, we obtain for each problem class conditions which guarantee local quadratic convergence of the general Newton-type algorithm and its special realizations to a solution of the particular problem. Moreover, we prove for FJ systems of GNEPs that generically some full row rank condition is satisfied at any solution of the FJ system of a GNEP. The latter condition implies the whole set of the convergence assumptions if the functions which characterize the GNEP are sufficiently smooth. Finally, we describe an idea for a possible globalization of our Newton-type methods, at least for the case that the constrained system arises from a certain smooth reformulation of the KKT system of a GNEP. More precisely, a hybrid method is presented whose local part is the LP-Newton method. The hybrid method turns out to be, under appropriate conditions, both globally and locally quadratically convergent.

Σε αυτή την εργασία, ασχολούμαστε με το πρόβλημα της επίλυσης συστημάτων μη γραμμικών αλγεβρικών ή/και υπερβατικών εξισώσεων και συγκεκριμένα αναφερόμαστε σε βελτιωμένες αλγοριθμικές τεχνικές επίλυσης τέτοιων συστημάτων. Μη γραμμικά συστήματα υπάρχουν σε πολλούς τομείς της επιστήμης, όπως στη Μηχανική, την Ιατρική, τη Χημεία, τη Ρομποτική, τα Οικονομικά, κ.τ.λ. Υπάρχουν πολλές μέθοδοι για την επίλυση συστημάτων μη γραμμικών εξισώσεων. Ανάμεσά τους η μέθοδος Newton είναι η πιο γνωστή μέθοδος, λόγω της τετραγωνικής της σύγκλισης όταν υπάρχει μια καλή αρχική εκτίμηση και ο Ιακωβιανός πίνακας είναι nonsingular. Η μέθοδος Newton έχει μερικά μειονεκτήματα, όπως τοπική σύγκλιση, αναγκαιότητα υπολογισμού του Ιακωβιανού πίνακα και ακριβής επίλυση του γραμμικού συστήματος σε κάθε επανάληψη. Σε αυτή τη μεταπτυχιακή διπλωματική εργασία αναλύουμε τη μέθοδο Newton και κατηγοριοποιούμε μεθόδους που συμβάλλουν στην αντιμετώπιση των μειονεκτημάτων της μεθόδου Newton, π.χ. Quasi-Newton και Inexact-Newton μεθόδους. Μερικές πιο πρόσφατες μέθοδοι που περιγράφονται σε αυτή την εργασία είναι η μέθοδος MRV και δύο νέες μέθοδοι Newton χωρίς άμεσες συναρτησιακές τιμές, κατάλληλες για προβλήματα με μη ακριβείς συναρτησιακές τιμές ή με μεγάλο υπολογιστικό κόστος. Στο τέλος αυτής της μεταπτυχιακής εργασίας, παρουσιάζουμε τις βασικές αρχές της Ανάλυσης Διαστημάτων και τη Διαστηματική μέθοδο Newton. / In this contribution, we deal with the problem of solving systems of nonlinear algebraic or/and transcendental equations and in particular we are referred to improved algorithmic techniques of such kind of systems. Nonlinear systems arise in many domains of science, such as Mechanics, Medicine, Chemistry, Robotics, Economics, etc. There are several methods for solving systems of nonlinear equations. Among them Newton's method is the most famous, because of its quadratic convergence when a good initial guess exists and the Jacobian matrix is nonsingular. Newton's method has some disadvantages, such as local convergence, necessity of computation of Jacobian matrix and the exact solution of linear system at each iteration. In this master thesis we analyze Newton's method and we categorize methods that contribute to the treatment of drawbacks of Newton's method, e.g. Quasi-Newton and Inexact-Newton methods. Some more recent methods which are described in this thesis are the MRV method and two new Newton's methods without direct function evaluations, ideal for problems with inaccurate function values or high computational cost. At the end of this master thesis, we present the basic principles of Interval Analysis and Interval Newton's method.

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.

Le but de cette thèse est d'étudier la méthode de Newton pour résoudre numériquement les inclusions variationnelles, appelées aussi dans la littérature les équations généralisées. Ces problèmes engendrent en général des opérateurs multivoques. La première partie est dédiée à l'extension des approches de Kantorovich et la théorie (alpha, gamma) de Smale (connues pour les équations non-linéaires classiques) au cas des inclusions variationnelles dans les espaces de Banach. Ceci a été rendu possible grâce aux développements récents des outils de l'analyse variationnelle et non-lisse tels que la régularité métrique. La seconde partie est consacrée à l'étude de méthodes numériques de type-Newton pour les inclusions variationnelles en utilisant la différentiabilité généralisée d'applications multivoques où nous proposons de linéariser à la fois les parties univoques (lisses) et multivoques (non-lisses). Nous avons montré que, sous des hypothèses sur les données du problème ainsi que le choix du point de départ, la suite générée par la méthode de Newton converge au moins linéairement vers une solution du problème de départ. La convergence superlinéaire peut-être obtenue en imposant plus de conditions sur l'approximation multivaluée. La dernière partie de cette thèse est consacrée à l'étude des équations généralisées dans les variétés Riemaniennes à valeurs dans des espaces euclidiens. Grâce à la relation entre la structure géométrique des variétés et les applications de rétractions, nous montrons que le schéma de Newton converge localement superlinéairement vers une solution du problème. La convergence quadratique (locale et semi-locale) peut-être obtenue avec des hypothèses de régularités sur les données du problème. / This thesis is devoted to present some results in the scope of Newton-type methods applied for inclusion involving set-valued mappings. In the first part, we follow the Kantorovich's and/or Smale's approaches to study the convergence of Josephy-Newton method for generalized equation (GE) in Banach spaces. Such results can be viewed as an extension of the classical Kantorovich's theorem as well as Smale's (alpha, gamma)-theory which were stated for nonlinear equations. The second part develops an algorithm using set-valued differentiation in order to solve GE. We proved that, under some suitable conditions imposed on the input data and the choice of the starting point, the algorithm produces a sequence converging at least linearly to a solution of considering GE. Moreover, by imposing some stronger assumptions related to the approximation of set-valued part, the proposed method converges locally superlinearly. The last part deals with inclusions involving maps defined on Riemannian manifolds whose values belong to an Euclidean space. Using the relationship between the geometric structure of manifolds and the retraction maps, we show that, our scheme converges locally superlinearly to a solution of the initial problem. With some more regularity assumptions on the data involved in the problem, the quadratic convergence (local and semi-local) can be ensured.

In this thesis we consider constrained systems of equations. The focus is on local Newton-type methods for the solution of constrained systems which converge locally quadratically under mild assumptions implying neither local uniqueness of solutions nor differentiability of the equation function at solutions. The first aim of this thesis is to improve existing local convergence results of the constrained Levenberg-Marquardt method. To this end, we describe a general Newton-type algorithm. Then we prove local quadratic convergence of this general algorithm under the same four assumptions which were recently used for the local convergence analysis of the LP-Newton method. Afterwards, we show that, besides the LP-Newton method, the constrained Levenberg-Marquardt method can be regarded as a special realization of the general Newton-type algorithm and therefore enjoys the same local convergence properties. Thus, local quadratic convergence of a nonsmooth constrained Levenberg-Marquardt method is proved without requiring conditions implying the local uniqueness of solutions. As already mentioned, we use four assumptions for the local convergence analysis of the general Newton-type algorithm. The second aim of this thesis is a detailed discussion of these convergence assumptions for the case that the equation function of the constrained system is piecewise continuously differentiable. Some of the convergence assumptions seem quite technical and difficult to check. Therefore, we look for sufficient conditions which are still mild but which seem to be more familiar. We will particularly prove that the whole set of the convergence assumptions holds if some set of local error bound conditions is satisfied and in addition the feasible set of the constrained system excludes those zeros of the selection functions which are not zeros of the equation function itself, at least in a sufficiently small neighborhood of some fixed solution. We apply our results to constrained systems arising from complementarity systems, i.e., systems of equations and inequalities which contain complementarity constraints. Our new conditions are discussed for a suitable reformulation of the complementarity system as constrained system of equations by means of the minimum function. In particular, it will turn out that the whole set of the convergence assumptions is actually implied by some set of local error bound conditions. In addition, we provide a new constant rank condition implying the whole set of the convergence assumptions. Particularly, we provide adapted formulations of our new conditions for special classes of complementarity systems. We consider Karush-Kuhn-Tucker (KKT) systems arising from optimization problems, variational inequalities, or generalized Nash equilibrium problems (GNEPs) and Fritz-John (FJ) systems arising from GNEPs. Thus, we obtain for each problem class conditions which guarantee local quadratic convergence of the general Newton-type algorithm and its special realizations to a solution of the particular problem. Moreover, we prove for FJ systems of GNEPs that generically some full row rank condition is satisfied at any solution of the FJ system of a GNEP. The latter condition implies the whole set of the convergence assumptions if the functions which characterize the GNEP are sufficiently smooth. Finally, we describe an idea for a possible globalization of our Newton-type methods, at least for the case that the constrained system arises from a certain smooth reformulation of the KKT system of a GNEP. More precisely, a hybrid method is presented whose local part is the LP-Newton method. The hybrid method turns out to be, under appropriate conditions, both globally and locally quadratically convergent.