Cette thèse traite des méthodes de descente d’ordre un pour les problèmes de minimisation. Elle comprend trois parties. Dans la première partie, nous apportons une vue d’ensemble des bornes d’erreur et les premières briques d’unification d’un concept. Nous montrons en effet la place centrale de l’inégalité du gradient de Lojasiewicz, en mettant en relation cette inégalité avec les bornes d’erreur. Dans la seconde partie, en usant de l’inégalité de Kurdyka-Lojasiewicz (KL), nous apportons un nouvel outil pour calculer la complexité des m´méthodes de descente d’ordre un pour la minimisation convexe. Notre approche est totalement originale et utilise une suite proximale “worst-case” unidimensionnelle. Ces résultats introduisent une méthodologie simple : trouver une borne d’erreur, calculer la fonction KL désingularisante quand c’est possible, identifier les constantes pertinentes dans la méthode de descente, et puis calculer la complexité en usant de la suite proximale “worst-case” unidimensionnelle. Enfin, nous étendons la méthode extragradient pour minimiser la somme de deux fonctions, la première étant lisse et la seconde convexe. Sous l’hypothèse de l’inégalité KL, nous montrons que la suite produite par la méthode extragradient converge vers un point critique de ce problème et qu’elle est de longueur finie. Quand les deux fonctions sont convexes, nous donnons la vitesse de convergence O(1/k) qui est classique pour la méthode de gradient. De plus, nous montrons que notre complexité de la seconde partie peut être appliquée à cette méthode. Considérer la méthode extragradient est l’occasion de d´écrire la recherche linéaire exacte pour les méthodes de décomposition proximales. Nous donnons des détails pour l’implémentation de ce programme pour le problème des moindres carrés avec régularisation ℓ1 et nous donnons des résultats numériques qui suggèrent que combiner des méthodes non-accélérées avec la recherche linéaire exacte peut être un choix performant. / This thesis focuses on first order descent methods in the minimization problems. There are three parts. Firstly, we give an overview on local and global error bounds. We try to provide the first bricks of a unified theory by showing the centrality of the Lojasiewicz gradient inequality. In the second part, by using Kurdyka- Lojasiewicz (KL) inequality, we provide new tools to compute the complexity of first-order descent methods in convex minimization. Our approach is completely original and makes use of a one-dimensional worst-case proximal sequence. This result inaugurates a simple methodology: derive an error bound, compute the KL esingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the one-dimensional worst case proximal sequence. Lastly, we extend the extragradient method to minimize the sum of two functions, the first one being smooth and the second being convex. Under Kurdyka-Lojasiewicz assumption, we prove that the sequence produced by the extragradient method converges to a critical point of this problem and has finite length. When both functions are convex, we provide a O(1/k) convergence rate. Furthermore, we show that our complexity result in the second part can be applied to this method. Considering the extragradient method is the occasion to describe exact line search for proximal decomposition methods. We provide details for the implementation of this scheme for the ℓ1 regularized least squares problem and give numerical results which suggest that combining nonaccelerated methods with exact line search can be a competitive choice.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Neste texto, serà apresentado um resultado proposto por Paulo Cordaro e Jorge Hounie sobre o decaimente do primeiro autovalor do operador de Laplace-Beltrami em uma superfÃcie de nÃvel conexa em Sn+1, n ≥1. Esta dissertaÃÃo baseia-se no artigo "The First Eingenvalue of Analytic Level Surfaces on Spheres"de Sagun Chanillo (Mathematical Reseach Letters, vol 1 (1994), p. 159-166). / In the text, will presented one resultad proposed by Paulo Cordaro and Jorge Hounie concerning the possible rate of decay of the first eigenvalue of Laplace-Beltrami operator on a level surface connected in Sn+1, n ≥ 1 This thesis is basead on the paper "The First Eingenvalue of Analytic Level Surfaces on Spheres"of Sagun Chanillo (Mathematical Reseach Letters, vol. 1 (1994), p. 159-166).

No description available.

This thesis considers regularized block multi-convex optimization, where the feasible set and objective function are generally non-convex but convex in each block of variables. I review some of its interesting examples and propose a generalized block coordinate descent (BCD) method. The generalized BCD uses three different block-update schemes. Based on the property of one block subproblem, one can freely choose one of the three schemes to update the corresponding block of variables. Appropriate choices of block-update schemes can often speed up the algorithm and greatly save computing time. Under certain conditions, I show that any limit point satisfies the Nash equilibrium conditions. Furthermore, I establish its global convergence and estimate its asymptotic convergence rate by assuming a property based on the Kurdyka-{\L}ojasiewicz inequality. As a consequence, this thesis gives a global linear convergence result of cyclic block coordinate descent for strongly convex optimization. The proposed algorithms are adapted for factorizing nonnegative matrices and tensors, as well as completing them from their incomplete observations. The algorithms were tested on synthetic data, hyperspectral data, as well as image sets from the CBCL, ORL and Swimmer databases. Compared to the existing state-of-the-art algorithms, the proposed algorithms demonstrate superior performance in both speed and solution quality.

Diese Arbeit befasst sich mit Untersuchung der Hölder Calmness, eines Stabilitätskonzeptes das man als Verallgemeinerung des Begriffs der Calmness erhält. Ausgehend von Charakterisierungen dieser Eigenschaft für Niveaumengen von Funktionen, werden, unter der Voraussetzung der Hölder Calmness, Prozeduren zur Bestimmung von Elementen dieser Mengen analysiert. Ebenso werden hinreichende Bedingungen für Hölder Calmness studiert. Da Hölder Calmness (nichtleerer) Lösungsmengen endlicher Ungleichungssysteme mittels (lokaler) Fehlerabschätzungen beschrieben werden kann, werden auch Erweiterungen der lokalen zu globalen Ergebnissen diskutiert. Als Anwendung betrachten wir speziell den Fall von Niveaumengen von Polynomen bzw. allgemeine Lösungsmengen polynomialer Gleichungen und Ungleichungen. Eine konkrete Frage, die wir beantworten wollen, ist die nach dem Zusammenhang zwischen dem größten Grad der beteiligten Polynome sowie dem Typ, d.h. dem auftretenden Exponenten, der Hölder Calmness des entsprechenden Systems. / This thesis is concerned with an analysis of Hölder calmness, a stability property derived from the concept of calmness. On the basis of its characterization for (sub)level sets, we will cogitate about procedures to determine points in such sets under a Hölder calmness assumption. Also sufficient conditions for Hölder calmness of (sub)level sets and of inequality systems will be given and examined. Further, since Hölder calmness of (nonempty) solution sets of finite inequality systems may be described in terms of (local) error bounds, we will as well amplify the local propositions to global ones. As an application we investigate the case of (sub)level sets of polynomials and of general solution sets of polynomial equations and inequalities. A concrete question we want to answer here is, in which way the maximal degree of the involved polynomials is connected to the exponent of Hölder calmness or of the error bound for the system in question.

L'objet de cette thèse est d'étudier le comportement en temps long de solutions d'équations d'évolution non locales ainsi que la limite singulière d'équations et de systèmes d'équations aux dérivées partielles, où intervient un petit paramètre epsilon. Au Chapitre 1, nous considérons une équation de réaction-diffusion non locale avec conservation au cours du temps de l'intégrale en espace de la solution; cette équation a été initialement proposée par Rubinstein et Sternberg pour modéliser la séparation de phase dans un mélange binaire. Le problème de Neumann associé possède une fonctionnelle de Lyapunov, c'est-à-dire une fonctionnelle qui décroit selon les orbites. Après avoir prouvé que la solution est confinée dans une région invariante, nous étudions son comportement en temps long. Nous nous appuyons sur une inégalité de Lojasiewicz pour montrer qu'elle converge vers une solution stationnaire quand t tend vers l'infini. Nous évaluons également le taux de la convergence et calculons précisément la solution stationnaire limite en dimension un d'espace. Le Chapitre 2 est consacré à l'étude de l'équation différentielle non locale que l'on obtient en négligeant le terme de diffusion dans l'équation d'Allen-Cahn non locale étudiée au Chapitre 1. Sans le terme de diffusion, la solution ne peut pas être plus régulière que la fonction initiale. C'est la raison pour laquelle on ne peut pas appliquer la méthode du Chapitre 1 pour l'étude du comportement en temps long de la solution. Nous présentons une nouvelle méthode basée sur la théorie des réarrangements et sur l'étude du profil de la solution. Nous montrons que la solution est stable pour les temps grands et présentons une caractérisation détaillée de sa limite asymptotique quand t tend vers l'infini. Plus précisément, la fonction limite est une fonction en escalier, qui prend au plus deux valeurs, qui coïncident avec les points stables d'une équation différentielle associée. Nous montrons aussi par un contre-exemple non trivial que, quand une hypothèse sur la fonction initiale n'est pas satisfaite, la fonction limite peut prendre trois valeurs, qui correspondent aux points instable et stables de l'équation différentielle associée. Nous étudions au Chapitre 3 une équation différentielle ordinaire non locale qui a éte proposée par M. Nagayama. Une difficulté essentielle est que le dénominateur dans le terme de réaction non local peut s'annuler. Nous appliquons un théorème de point fixe lié a une application contractante pour démontrer que le problème à valeur initiale correspondant possède une solution unique qui reste connée dans un ensemble invariant. Ce problème possède une fonctionnelle de Lyapunov, qui est un ingrédient essentiel pour démontrer que la solution converge vers une solution stationnaire constante par morceaux quand t tend vers l'infini. Au Chapitre 4, nous considérons un modèle d'interface diffuse pour la croissance de tumeurs, où intervient une équation d'ordre quatre de type Cahn Hilliard. Après avoir introduit un modèle de champ de phase associé, on étudie formellement la limite singulière de la solution quand le coefficient du terme de réaction tend vers l'infini. Plus précisément, nous montrons que la solution converge vers la solution d'un problème à frontière libre. AMS subject classifications. 35K57, 35K50, 35K20, 35R35, 35R37, 35B40, 35B25. / The aim of this thesis is to study the large time behavior of solutions of nonlocal evolution equations and to also study the singular limit of equations and systems of parabolic partial differential equations involving a small parameter epsilon. In Chapter 1, we consider a nonlocal reaction-diffusion equation with mass conservation, which was originally proposed by Rubinstein and Sternberg as a model for phase separation in a binary mixture. The corresponding Neumann problem possesses a Lyapunov functional, namely a functional which decreases in time along solution orbits. After having proved that the solution is conned in an invariant region, we study its large time behavior and apply a Lojasiewicz inequality to show that it converges to a stationary solution as t tends to infinity. We also evaluate the rate of convergence and precisely compute the limiting stationary solution in one space dimension. Chapter 2 is devoted to the study of a nonlocal evolution equation which one obtains by neglecting the diffusion term in the nonlocal Allen-Cahn equation studied in Chapter 1. Without the diffusion term, the solution can not be expected to be more regular than the initial function. Moreover, because of the absence of the diusion term, the method of Chapter 1 can not be applied to study the large time behavior of the solution. We present a new method based up on rearrangement theory and the study of the solution profile. We show that the solution stabilizes for large times and give a detailed characterization of its asymptotic limit as t tends to infinity. More precisely, it turns out that the limiting function is a step function, which takes at most two values, which are stable points of a corresponding ordinary dierential equation. We also show by means of a nontrivial counterexample that, when a certain hypothesis on the initial function does not hold, the limiting function may take three values. One of them is the unstable point and the two others are the stable points of the ordinary dierential equation. We study in Chapter 3 a nonlocal ordinary dierential equation which has been proposed by M. Nagayama. The nonlocal term involves a denominator which may vanish. We apply a contraction fixed point theorem to prove the existence of a unique solution which stays confined in an invariant region. We also show that the corresponding initial value problem possesses a Lyapunov functional and prove that the solution stabilizes for large times to a step function, which takes at most two values. In Chapter 4, we consider a diffuse-interface tumor-growth model which involves a fourth order Cahn-Hilliard type equation. Introducing a related phase-field model, we formally study the singular limit of the solution as the reaction coecient tends to infinity. More precisely, we show that the solution converges to the solution of a moving boundary problem. AMS subject classifications. 35K57, 35K50, 35K20, 35R35, 35R37, 35B40, 35B25.