Academic literature on the topic 'Itération des fonction unimodales'

Depuis quelques années, des véhicules de cartographie mobile ont été développés pour acquérir des données géoréférencées très précises et en grande quantité au niveau du canyon urbain. L'application majeure des données collectées par ces véhicules est d'améliorer les bases de données géographiques existantes, en particulier leur précision, leur niveau de détail et la diversité des objets représentés. On peut citer entre autres applications la modélisation géométrique fine et la texturation des façades, l'extraction de "petits" objets comme les troncs d'arbres, poteaux, panneaux, mobiliers urbain, véhicules,...Cependant, les systèmes de géopositionnement de ces véhicules ne parviennent pas à fournir une localisation d'une précision suffisante pour cette tâche. En particulier, les masques GPS fréquents en milieu urbain sont paliés par les mesures de la centrale inertielle grâce à un algorithme de fusion de données pouvant entraîner une dérive. C'est pourquoi, un recalage est indispensable pour mettre en correspondance ces données mobiles très détaillées avec les bases de données géographiques moins détaillées mais mieux géopositionnées, qu'elles soient 2D ou 3D.Cet article présente une méthode générique et efficace permettant un tel recalage. Le processus est basé sur une méthode de type ICP ("Iterative Closest Point") point à plan.On suppose que l'erreur de géopositionnement, ou dérivevarie de façon non linéaire, mais lentement en fonction du temps. On modélise donc la trajectoire par une "chaîne" ayant une certaine rigidité. A chaque itération, la trajectoire est déformée afin de minimiser la distance des points laser aux primitives planes du modèle.Cette méthode permet d'approximer la dérive par une fonction linéaire par intervalle de temps.La méthode est testée sur des données réelles ( 3,6 millions de points laser acquis sur un quartier de la ville de Paris sont recalés sur un modèle 3D d'environ 71.400 triangles). Enfin, la robustesse et la précision de cet algorithme sont évaluées et discutées.

International audience To find an optimal domain is equivalent to look for Its characteristic function. At first sight this problem seems to be nondifferentiable. But it is possible to derive the variation of a cost function when we switch the characteristic function from 0 to 1 or from 1 to 0 a small area. Classical and two generalized adjoint approaches are considered in this paper. Their domain of validity is given and Illustrated by several examples. Using this gradient type Information, It is possible to build fast algorithms. Generally, only one Iteration Is needed to find the optimal shape. Trouver un domaine optimal est équivalent à la recherche de sa fonction caractéristique. A première vue, ce problème semble non différentiable, mais Il est possible de calculer la variation de la fonction coût lorsque la fonction caractéristique passe de 1 à 0 ou de 0 à 1 dans une région de petite taille. On s’appuiera sur une approche adjointe classique et deux généralisations de cette méthode. Le domaine de validité de ces différentes approches est donné et illustré par différents exemples. Cette Information de type gradient permet de construire des algorithmes très efficaces: en général, une seule Itération suffit pour trouver le domaine optimal.

Cette thèse propose une alternative à la parallélisation de GMRES préconditionné par Schwarz multiplicatif par la technique de coloriage de graphe adjacent à la matrice. Cette parallélisation suppose que le graphe adjacent à la matrice est partitionné selon une direction. A partir de ce partionnement on peut dériver une forme explicite pour l'itération de Schwarz multiplicatif. On utilise cette forme explicite dans un pipeline pour la construction de l'espace de Krylov. On conserve les qualités du pipeline, en évitant d'inserrer les points de synchronisation comme les produits scalaires globaux dans le procédé d'Arnoldi. Pour cela, on utilise une version de GMRES qui découple la construction de l'espace de Krylov et la factorisation QR dans le procédé d'Arnoldi. Tous ces algorithmes sont implémentés sur le standard PETSc et portent le nom de GPREMS (Gmres PREconditionned by multiplicatif Schwarz). Les tests sont réalisés sur des problèmes issus de la simulation de semiconducteurs et de la mécanique des fluides. Cette validation numérique confirme les qualités parallèles de notre code, mais aussi sa compétitivité par rapport aux autres préconditionneurs du type décomposition de domaine comme Schwarz additif ou le complément de Schur<br>This thesis proposes an alternative to the parallelization of GMRES preconditioned by multiplicative Schwarz by the technique of coloring adjacent graph to the matrix. This parallelization implies that the adjacent graph to the matrix is partitioned according to one direction. From this partitioning we can derive an explicit form of spliting of multiplicatif Schwarz. We use this explicite form in a pipeline for the construction of Krylov subspace basis. The qualities of the pipeline are prevent by avoiding a synchronization points due to the dot product in overall process Arnoldi. For this reason, we use a version of GMRES which decouples the construction of the space Krylov and QR factorization in the process Arnoldi. All these algorithms are implemented on standard PETSc and bears the name of GPREMS (GMRES PREconditoned by multiplicative Schwarz). The tests are performed on problems arising from the simulation of semiconductors and fluid mechanics. This validation confirms the parallel qualities of our code, but also its competitiveness with other preconditioner type domain decomposition as Schwarz additive or additional Schur

Cette thèse traite de généralisations et de raffinements de l'algorithme d'itération sur les politiques, ou algorithme de Howard, apparu à la fin des années 50 pour la résolution de problèmes de contrôle stochastique. Nous montrons que l'itération sur les politiques permet de résoudre bien d'autres problèmes de décision faisant intervenir des opérateurs de programmation dynamique monotones contractants pour la norme sup. Nous donnons un algorithme universel d'itération sur les politiques, calculant le point fixe d'une application décrite comme infimum d'un ensemble rectangulaire clos inférieurement d'applications monotones contractantes, ce qui fournit un théorème constructif de point-fixe. Pour les opérateurs de jeux déterministes ou stochastiques répétés, nous donnons un algorithme pour le calcul d'un vecteur propre non-linéaire, ou de demi-droites invariantes, permettant de calculer le taux de croissance asymptotique de la fonction valeur du jeu. Les preuves s'appuient sur des résultats de théorie spectrale des applications monotones contractantes, généralisant la théorie spectrale max-plus. Nous spécialisons enfin au cas déterministe l'algorithme classique de Howard, ce qui permet de résoudre des problèmes de théorie des graphes. Pour le calcul d'un circuit de poids moyen maximal, on obtient un algorithme dont la performance est en moyenne (expérimentalement) presque linéaire, ce qui gagne en moyenne un ordre de grandeur par rapport aux algorithmes existants, comme l'algorithme de Karp. Pour les problèmes de plus courts chemins, on obtient un nouvel algorithme de temps 0(nm), où n est le nombre de sommets, et m le nombre d'arcs, qui n'est expérimentalement pas plus rapide que les méthodes usuelles (Bellman, Ford-Bellman), mais permet cependant la détection rapide d'éventuels circuits de poids positifs.

Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), ajoute à LSPI un concept venant de [lambda]-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LS[lambda]PI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lorincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008<br>This thesis studies policy iteration methods with linear approximation of the value function for large state space problems in the reinforcement learning context. We first introduce a unified algorithm that generalizes the main stochastic optimal control methods. We show the convergence of this unified algorithm to the optimal value function in the tabular case, and a performance bound in the approximate case when the value function is estimated. We then extend the literature of second-order linear approximation algorithms by proposing a generalization of Least-Squares Policy Iteration (LSPI) (Lagoudakis and Parr, 2003). Our new algorithm, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), adds to LSPI an idea of [lambda]-Policy Iteration (Bertsekas and Ioffe, 1996): the damped (or optimistic) evaluation of the value function, which allows to reduce the variance of the estimation to improve the sampling efficiency. Thus, LS[lambda]PI offers a bias-variance trade-off that may improve the estimation of the value function and the performance of the policy obtained. In a second part, we study in depth the game of Tetris, a benchmark application that several works from the literature attempt to solve. Tetris is a difficult problem because of its structure and its large state space. We provide the first full review of the literature that includes reinforcement learning works, evolutionary methods that directly explore the policy space and handwritten controllers. We observe that reinforcement learning is less successful on this problem than direct policy search approaches such as the cross-entropy method (Szita et Lorincz, 2006). We finally show how we built a controller that outperforms the previously known best controllers, and shortly discuss how it allowed us to win the Tetris event of the 2008 Reinforcement Learning Competition

Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), ajoute à LSPI un concept venant de λ-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LSλPI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lőrincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008.

Cette thèse est consacrée à l'étude des opérateurs de composition sur les espaces modèles. Soit [Phi] une fonction analytique du disque unité dans lui-même et soit [Théta] une fonction intérieure, c'est à dire une fonction holomorphe et bornée par 1 dont les limites radiales sur le cercle sont de module 1 presque partout par rapport à la mesure de Lebesgue. A cette fonction [Théta], on associe l'espace modèle K[Théta], défini comme l'ensemble des fonctions f ∈ H² qui sont orthogonales au sous-espace [Théta]H². Ici H² est l'espace de Hardy du disque unité. Ces sous-espaces sont importants en théorie des opérateurs car ils servent à modéliser une large classe de contractions sur un espace de Hilbert. Le premier problème auquel nous nous intéressons concerne la compacité d'un opérateur de composition C[Phi] vu comme opérateur de K[Théta], dans H². Récemment, Lyubarskii et Malinnikova ont obtenu un joli critère de compacité pour ces opérateurs qui fait intervenir la fonction de comptage de Nevanlinna du symbole [Phi]. Ce critère généralise le critère classique de Shapiro. Dans une première partie de la thèse, nous généralisons ce résultat de Lyubarskii-Malinnikova à une classe plus générale de sous-espaces, à savoir les espaces de de Branges-Rovnyak ou certains de leurs sous-espaces. Les techniques utilisées sont en particulier des inégalités fines de type Bernstein pour ces espaces. Le deuxième problème auquel nous nous intéressons dans cette thèse concerne l'invariance de K[Théta] sous l'action de C [Phi]. Ce problème nous amène à considérer une structure de groupe sur le disque unité du plan complexe via les automorphismes qui fixent le point 1. A travers cette action de groupe, chaque point du disque produit une classe d'équivalence qui se trouve être une suite de Blaschke. On montre alors que les produits de Blaschke correspondant sont des solutions "minimales" d'une équation fonctionnelle [Psi]°[Phi]=[Lambda][Psi], où [Lambda] est une constante unimodulaire et [Phi] un automorphisme du disque unité. Ces résultats sont ensuite appliqués au problème d'invariance d'un espace modèle par un opérateur de composition<br>This thesis concerns the study of composition operators on model spaces. Let [Phi] be an analytic function on the unit disk into itself and let [Théta] be an inner function, that is a holomorphic function bounded by 1 such that the radial limits on the unit circle are of modulus 1 almost everywhere with respect to Lebesgue measure. With this function [Théta], we associate the model space K[Théta], defined as the set of functions f ∈ H², which are orthogonal to the subspace [Théta]H². Here H² is the Hardy space on the unit disc. These subspaces are important in operator theory because they are used to model a large class of contractions on Hilbert space. The first problem which we are interested in concerns the compactness of the composition operator C[Phi] as an operator on H² into H². Recently, Lyubarskii and Malinnikova have obtained a nice criterion for the compactness of these operators which is related to the Nevanlinna counting function. This criterion generalizes the classical criterion of Shapiro. In the first part of the thesis, we generalize this result of Lyubarskii-Malinnikova to a more general class of subspaces, known as de Branges-Rovnyak spaces or some subspaces of them. The techniques that are used are particular Bernstein type inequalities of these spaces.The second problem in which we are interested in this thesis concerns the invariance of K[Théta] under C[Phi]. We present a group structure on the unit disc via the automorphisms which fix the point 1. Then, through theinduced group action, each point of the unit disc produces an equivalence class which turns out to be a Blaschke sequence. Moreover, the corresponding Blaschke products are minimal solutions of the functional equation [Psi]°[Phi]=[Lambda][Psi] where [Lambda] is a unimodular constant and is an automorphism of the unit disc. These results are applied in the invariance problem of the model spaces by the composition operator

En fiabilité et en analyse de survie, les distributions qui ont une fonction de hasard unimodale ne sont pas nombreuses, qu'on peut citer: Gaussienne inverse ,log-normale, log-logistique, de Birnbaum-Saunders, de Weibull exponentielle et de Weibullgénéralisée. Dans cette thèse, nous développons les tests modifiés du Chi-deux pour ces distributions tout en comparant la distribution Gaussienne inverse avec les autres. Ensuite nousconstruisons le modèle AFT basé sur la distribution Gaussienne inverse et les systèmes redondants basés sur les distributions de fonction de hasard unimodale<br>In reliability and survival analysis, distributions that have a unimodalor $\cap-$shape hazard rate function are not too many, they include: the inverse Gaussian,log-normal, log-logistic, Birnbaum-Saunders, exponential Weibull and power generalized Weibulldistributions. In this thesis, we develop the modified Chi-squared tests for these distributions,and we give a comparative study between the inverse Gaussian distribution and the otherdistributions, then we realize simulations. We also construct the AFT model based on the inverseGaussian distribution and redundant systems based on distributions having a unimodal hazard ratefunction

Les progrès en termes de puissance de calcul ont entraîné de nombreuses évolutions dans le domaine de la science et de ses applications. La résolution de systèmes linéaires survient fréquemment dans le calcul scientifique, comme par exemple lors de la résolution d'équations aux dérivées partielles par la méthode des éléments finis. Le temps de résolution découle alors directement des performances des opérations algébriques mises en jeu.Cette thèse a pour but de développer des algorithmes parallèles innovants pour la résolution de systèmes linéaires creux de grandes tailles. Nous étudions et proposons comment calculer efficacement les opérations d'algèbre linéaire sur plateformes de calcul multi-coeur hétérogènes-GPU afin d'optimiser et de rendre robuste la résolution de ces systèmes. Nous proposons de nouvelles techniques d'accélération basées sur la distribution automatique (auto-tuning) des threads sur la grille GPU suivant les caractéristiques du problème et le niveau d'équipement de la carte graphique, ainsi que les ressources disponibles. Les expérimentations numériques effectuées sur un large spectre de matrices issues de divers problèmes scientifiques, ont clairement montré l'intérêt de l'utilisation de la technologie GPU, et sa robustesse comparée aux bibliothèques existantes comme Cusp.L'objectif principal de l'utilisation du GPU est d'accélérer la résolution d'un problème dans un environnement parallèle multi-coeur, c'est-à-dire "Combien de temps faut-il pour résoudre le problème?". Dans cette thèse, nous nous sommes également intéressés à une autre question concernant la consommation énergétique, c'est-à-dire "Quelle quantité d'énergie est consommée par l'application?". Pour répondre à cette seconde question, un protocole expérimental est établi pour mesurer la consommation d'énergie d'un GPU avec précision pour les opérations fondamentales d'algèbre linéaire. Cette méthodologie favorise une "nouvelle vision du calcul haute performance" et apporte des réponses à certaines questions rencontrées dans l'informatique verte ("green computing") lorsque l'on s'intéresse à l'utilisation de processeurs graphiques.Le reste de cette thèse est consacré aux algorithmes itératifs synchrones et asynchrones pour résoudre ces problèmes dans un contexte de calcul hétérogène multi-coeur-GPU. Nous avons mis en application et analysé ces algorithmes à l'aide des méthodes itératives basées sur les techniques de sous-structurations. Dans notre étude, nous présentons les modèles mathématiques et les résultats de convergence des algorithmes synchrones et asynchrones. La démonstration de la convergence asynchrone des méthodes de sous-structurations est présentée. Ensuite, nous analysons ces méthodes dans un contexte hybride multi-coeur-GPU, qui devrait ouvrir la voie vers les méthodes hybrides exaflopiques.Enfin, nous modifions la méthode de Schwarz sans recouvrement pour l'accélérer à l'aide des processeurs graphiques. La mise en oeuvre repose sur l'accélération par les GPUs de la résolution locale des sous-systèmes linéaires associés à chaque sous-domaine. Pour améliorer les performances de la méthode de Schwarz, nous avons utilisé des conditions d'interfaces optimisées obtenues par une technique stochastique basée sur la stratégie CMA-ES (Covariance Matrix Adaptation Evolution Strategy). Les résultats numériques attestent des bonnes performances, de la robustesse et de la précision des algorithmes synchrones et asynchrones pour résoudre de grands systèmes linéaires creux dans un environnement de calcul hétérogène multi-coeur-GPU<br>Advances in computational power have led to many developments in science and its applications. Solving linear systems occurs frequently in scientific computing, as in the finite element discretization of partial differential equations. The running time of the overall resolution is a direct result of the performance of the involved algebraic operations.In this dissertation, different ways of efficiently solving large and sparse linear systems are put forward. We present the best way to effectively compute linear algebra operations in an heterogeneous multi-core-GPU environment in order to make solvers such as iterative methods more robust and therefore reduce the computing time of these systems. We propose new techniques to speed algorithms up the auto-tuning of the threading design, according to the problem characteristics and the equipment level in the hardware and available resources. Numerical experiments performed on a set of large-size sparse matrices arising from diverse engineering and scientific problems, have clearly shown the benefit of the use of GPU technology to solve large sparse systems of linear equations, and its robustness and accuracy compared to existing libraries such as Cusp.The main priority of the GPU program is computational time to obtain the solution in a parallel environment, i.e, "How much time is needed to solve the problem?". In this thesis, we also address another question regarding energy issues, i.e., "How much energy is consumed by the application?". To answer this question, an experimental protocol is established to measure the energy consumption of a GPU for fundamental linear algebra operations accurately. This methodology fosters a "new vision of high-performance computing" and answers some of the questions outlined in green computing when using GPUs.The remainder of this thesis is devoted to synchronous and asynchronous iterative algorithms for solving linear systems in the context of a multi-core-GPU system. We have implemented and analyzed these algorithms using iterative methods based on sub-structuring techniques. Mathematical models and convergence results of synchronous and asynchronous algorithms are presented here, as are the convergence results of the asynchronous sub-structuring methods. We then analyze these methods in the context of a hybrid multi-core-GPU, which should pave the way for exascale hybrid methods.Lastly, we modify the non-overlapping Schwarz method to accelerate it, using GPUs. The implementation is based on the acceleration of the local solutions of the linear sub-systems associated with each sub-domain using GPUs. To ensure good performance, optimized conditions obtained by a stochastic technique based on the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) are used. Numerical results illustrate the good performance, robustness and accuracy of synchronous and asynchronous algorithms to solve large sparse linear systems in the context of an heterogeneous multi-core-GPU system

Cette thèse rassemble plusieurs articles ayant pour sujet l'étude de la dynamique d'une large classe de réseaux d'automates. Deux outils sont introduits: les invariants algébriques associés à l'évolution temporelle; la fonction d'énergie permettant de déterminer l'évolution du réseau, tant en régime transitoire qu'en régime stationnaire. Finalement, nous étudions des réseaux unidimensionnels, la dynamique d'un automate à mémoire et les réseaux des fonctions booléennes à deux variables