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.

OLIVEIRA, José Anastácio de. Decaimento do primeiro autovalor do operador de Laplace-Beltrami em superfícies de nível analíticas na esfera. 2016. 51 f. Dissertação (Mestrado em Matemática)- Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Rocilda Sales (rocilda@ufc.br) on 2016-06-22T13:32:30Z No. of bitstreams: 1 2016_dis_jaoliveira.pdf: 849786 bytes, checksum: 82f035323806adc5483c8bdff1b1231f (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-06-22T13:35:16Z (GMT) No. of bitstreams: 1 2016_dis_jaoliveira.pdf: 849786 bytes, checksum: 82f035323806adc5483c8bdff1b1231f (MD5) / Made available in DSpace on 2016-06-22T13:35:16Z (GMT). No. of bitstreams: 1 2016_dis_jaoliveira.pdf: 849786 bytes, checksum: 82f035323806adc5483c8bdff1b1231f (MD5) Previous issue date: 2016 / 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). / 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).

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).

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-05-14T15:48:06Z No. of bitstreams: 2 Dissertação - Pedro Bonfim de Assunção Filho - 2015.pdf: 1595722 bytes, checksum: f3fd3bdb8a9b340d60e156dcf07a9d63 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-05-14T15:51:54Z (GMT) No. of bitstreams: 2 Dissertação - Pedro Bonfim de Assunção Filho - 2015.pdf: 1595722 bytes, checksum: f3fd3bdb8a9b340d60e156dcf07a9d63 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-05-14T15:51:54Z (GMT). No. of bitstreams: 2 Dissertação - Pedro Bonfim de Assunção Filho - 2015.pdf: 1595722 bytes, checksum: f3fd3bdb8a9b340d60e156dcf07a9d63 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-02-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work, based in [1, 18], we study the convergence of method of proximal point (MPP) regularized by a quasi-distance, applied to an optimization problem. The objective function considered not is necessarily convex and satisfies the property of Kurdyka- Lojasiewicz around by their generalized critical points. More specifically, we will show that any limited sequence, generated from MPP, converge the a generalized critical point. / Neste trabalho, baseado em [1, 18], estudamos a convergência do método do ponto proximal (MPP) regularizado por uma quase-distância aplicado a um problema de otimização. A função objetivo considerada não é necessariamente convexa e satisfaz a propriedade de Kurdyka-Lojasiewicz ao redor de seus pontos críticos generalizados. Mais precisamente, mostraremos que qualquer sequência limitada, gerada pelo MPP, converge a um ponto crítico generalizado.

<p>We study decentralized multiagent optimization over networks modeled as undirected</p> <p>graphs. The optimization problem consists of minimizing a (non convex) smooth function</p> <p>plus a convex extended-value function, which enforces constraints or extra structure on the</p> <p>solution (e.g., sparsity, low-rank). We further assume that the objective function satisfies the</p> <p>Kurdyka- Lojasiewicz (KL) property, with exponent in [0, 1). The KL property is satisfied</p> <p>by several (non convex) functions of practical interest, e.g., arising from machine learning</p> <p>applications; in the centralized setting, it permits to achieve strong convergence guarantees.</p> <p>Here we establish a first convergence result of the same type for distributed algorithms,</p> <p>specifically the distributed gradient-tracking based algorithm SONATA, first proposed in</p> <p>[ 1 ]. When exponent is in (0, 1/2], the sequence generated by SONATA is proved to converge to a</p> <p>stationary solution of the problem at an R-linear rate whereas sublinear rate is certified</p> <p>when KL exponent is in (1/2, 1). This matches the convergence behaviour of centralized proximal-gradient</p> <p>algorithms. Numerical results validate our theoretical findings.</p>

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'objectif principal de cette thèse concerne l'étude du comportement asymptotique des solutions globales de quelques équations, et systèmes couplés des équations, d'évolutions non linéaires avec différents types d'amortissements et des conditions sur le bord. Sous la condition basique que la non linéarité est analytique, on prouve que les énergies associées vérifient des inégalités de type Lojasiewicz et on obtient des résultats de convergence avec l'estimation de la vitesse de convergence. Pour tous les modèles étudiés dans cette thèse, on s'intéresse aux questions d'existence et d'unicité des solutions bornées à images relativement compactes dans leur espace d'énergie naturelles. Cette thèse est constituée de trois parties principales. Dans la première partie on prouve un résultat de convergence général avec l'estimation du taux de décroissance des solutions bornées d'une équation d'évolution abstraite non autonome avec dissipation linéaire. Le résultat permet de retrouver et généraliser de manière naturelle des résultats connus mais aussi il s'applique à une classe très générale des équations et des systèmes couplés avec divers types de couplages et avec diverses conditions sur le bord. La deuxième partie est consacrée à l'étude des équations du second ordre avec dissipation non linéaire et des conditions dynamiques classiques sur le bord. On prouve l'existence et l'unicité des solutions globales bornées à images relativement compactes et on montre la convergence vers un équilibre. Finalement, on s'intéresse à des équations d'évolution dégénérées de type hyperbolique-parabolique avec des conditions dynamiques de type mémoire sur le bord. On prouve l'existence et l'unicité des solutions globales bornées à images relativement compactes et on prouve la convergence avec l'estimation de la vitesse de convergence. Le premier chapitre de cette thèse consiste en une introduction préliminaire développant non seulement l'histoire des recherches reliées à nos modèles et leurs résultats décrits dans la littérature, mais aussi en présentant les énoncés de nos résultats obtenus avec les idées des démonstrations. On y discute la complexité de la problématique et l'on y présente la justification de l'étude / The main goal of this thesis is the study of the asymptotic behavior of global solutions to some nonlinear evolutions equations and coupled systems with different types of dissipation and boundary conditions. Under the assumption that the non-linear term is real analytic, we construct an appropriate Lyapunov energy and we use the Lojasiewicz-Simon inequality to show the convergence, and the convergence, and the convergence rate, of global weak solutions to single steady states. For all models studied in this thesis, we are in addition interested in the questions of the existence and uniqueness of global bounded solutions having relatively compact range in the natural energy space. This thesis consists of three main parts. In the first part, we present a unified approach to study the asymptotic behavior and the decay rate to a steady state of bounded weak solutions for an abstract non-autonomous nonlinear equation with linear dissipation. This result allows us to find and to generalize, in a natural way, known results but it applies to a quite general class of equations and coupled systems with different kinds of coupling and various boundary conditions. The second part is devoted to the study of a nonautonomous semilinear second order equation with nonlinear dissipation and a dynamical boundary condition. We prove the existence and uniqueness of global, bounded, weak solutions having relatively compact range in the natural energy space and we show that every weak solution converges to equilibrium. Finally, we consider a nonautonomous, semilinear, hyperbolic-parabolic equation subject to a dynamical boundary condition of memory type. We prove the existence and uniqueness of global bounded solutions having relatively compact range and we show the convergence of global weak solutions to single steady states. We prove also an estimate for the convergence rate. The first chapter of this thesis consist of a preliminary introduction developing not only the story of researches linked to our models and the results described in the literature, but presenting also our main results as well the ideas of their proofs. There we discuss the complexity of our problems and we present a justification for our studies

No description available.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-02-22T12:12:47Z No. of bitstreams: 2 Tese - Valdinês Leite de Sousa Júnior - 2017.pdf: 2145153 bytes, checksum: 388666d9bc1ff5aa261882785a3cc5e0 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-02-22T13:04:40Z (GMT) No. of bitstreams: 2 Tese - Valdinês Leite de Sousa Júnior - 2017.pdf: 2145153 bytes, checksum: 388666d9bc1ff5aa261882785a3cc5e0 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-02-22T13:04:40Z (GMT). No. of bitstreams: 2 Tese - Valdinês Leite de Sousa Júnior - 2017.pdf: 2145153 bytes, checksum: 388666d9bc1ff5aa261882785a3cc5e0 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-02-03 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / In this work, we investigate four different types of descent methods: a dual descent method in the scalar context and a multiobjective proximal point methods (one exact and two inexact versions). The first one is restricted to functions that satisfy the Kurdyka-Lojasiewicz property, where it is used a quasi-distance as a regularization function. In the next three methods, the objective is to study the convergence of a multiobjective proximal methods (exact an inexact) for a particular class of multiobjective functions that are not necessarily differentiable. For the inexact methods, we choose a proximal distance as the regularization term. Such a well-known distance allows us to analyze the convergence of the method under various settings. Applications in behavioral sciences are analyzed in the sense of the variational rationality approach. / Neste trabalho, investigaremos quatro tipos diferentes de métodos de descida: um método de descida dual e três versões do método do ponto proximal (exato e inexato) em otimização multiobjetivo. No primeiro, a análise de convergência será restrita a funções que satisfazem a propriedade Kurdyka-Lojasiewicz, onde é usada uma quase-distância como função regularizadora. Nos seguintes, o objetivo é estudar a convergência de uma versão exata e duas versões inexatas do método de ponto proximal em otimização multiobjetivo para uma classe particular de funções multiobjetivo que não são necessariamente diferenciáveis. Para os métodos inexatos, escolhemos uma distância proximal como termo regularizador. Aplicações em ciência comportamental serão analisadas no sentido da abordagem da teoria de racionalidade variacional.

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.