Dissertations / Theses: 'Algorithmes de Newton stochastiques'

1

Lu, Wei. "Μéthοdes stοchastiques du secοnd οrdre pοur le traitement séquentiel de dοnnées massives." Electronic Thesis or Diss., Normandie, 2024. http://www.theses.fr/2024NORMIR13.

Full text

Abstract:

Avec le développement rapide des technologies et l'acquisition de données de plus en plus massives, les méthodes capables de traiter les données de manière séquentielle (en ligne) sont devenues indispensables. Parmi ces méthodes, les algorithmes de gradient stochastique se sont imposés pour estimer le minimiseur d'une fonction exprimée comme l'espérance d'une fonction aléatoire. Bien qu'ils soient devenus incontournables, ces algorithmes rencontrent des difficultés lorsque le problème est mal conditionné. Dans cette thèse, nous nous intéressons sur les algorithmes stochastiques du second ordre, tels que ceux de type Newton, et leurs applications à diverses problématiques statistiques et d'optimisation. Après avoir établi des bases théoriques et exposé les motivations qui nous amènent à explorer les algorithmes de Newton stochastiques, nous développons les différentes contributions de cette thèse. La première contribution concerne l'étude et le développement d'algorithmes de Newton stochastiques pour la régression linéaire ridge et la régression logistique ridge. Ces algorithmes sont basés sur la formule de Riccati (Sherman-Morrison) pour estimer récursivement l'inverse de la Hessienne. Comme l'acquisition de données massives s'accompagne généralement d'une contamination de ces dernières, on s'intéresse, dans une deuxième contribution, à l'estimation en ligne de la médiane géométrique, qui est un indicateur robuste, i.e. peu sensible à la présence de données atypiques. Plus précisément, nous proposons un nouvel estimateur de Newton stochastique pour estimer la médiane géométrique. Dans les deux premières contributions, les estimateurs des inverses de Hessienne sont construits à l'aide de la formule de Riccati, mais cela n'est possible que pour certaines fonctions. Ainsi, notre troisième contribution introduit une nouvelle méthode de type Robbins-Monro pour l'estimation en ligne de l'inverse de la Hessienne, nous permettant ensuite de développer des algorithmes de Newton stochastiques dits universels. Enfin, notre dernière contribution se focalise sur des algorithmes de type Full Adagrad, où la difficulté réside dans le fait que l'on a un pas adaptatif basé sur la racine carré de l'inverse de la variance du gradient. On propose donc un algorithme de type Robbins-Monro pour estimer cette matrice, nous permettant ainsi de proposer une approche récursive pour Full AdaGrad et sa version streaming, avec des coûts de calcul réduits. Pour tous les nouveaux estimateurs que nous proposons, nous établissons leurs vitesses de convergence ainsi que leur efficacité asymptotique. De plus, nous illustrons l'efficacité de ces algorithmes à l'aide de simulations numériques et en les appliquant à des données réelles
With the rapid development of technologies and the acquisition of big data, methods capable of processing data sequentially (online) have become indispensable. Among these methods, stochastic gradient algorithms have been established for estimating the minimizer of a function expressed as the expectation of a random function. Although they have become essential, these algorithms encounter difficulties when the problem is ill-conditioned. In this thesis, we focus on second-order stochastic algorithms, such as those of the Newton type, and their applications to various statistical and optimization problems. After establishing theoretical foundations and exposing the motivations that lead us to explore stochastic Newton algorithms, we develop the various contributions of this thesis. The first contribution concerns the study and development of stochastic Newton algorithms for ridge linear regression and ridge logistic regression. These algorithms are based on the Riccati formula (Sherman-Morrison) to recursively estimate the inverse of the Hessian. As the acquisition of big data is generally accompanied by a contamination of the latter, in a second contribution, we focus on the online estimation of the geometric median, which is a robust indicator, i.e., not very sensitive to the presence of atypical data. More specifically, we propose a new stochastic Newton estimator to estimate the geometric median. In the first two contributions, the estimators of the Hessians' inverses are constructed using the Riccati formula, but this is only possible for certain functions. Thus, our third contribution introduces a new Robbins-Monro type method for online estimation of the Hessian's inverse, allowing us then to develop universal stochastic Newton algorithms. Finally, our last contribution focuses on Full Adagrad type algorithms, where the difficulty lies in the fact that there is an adaptive step based on the square root of the inverse of the gradient's covariance. We thus propose a Robbins-Monro type algorithm to estimate this matrix, allowing us to propose a recursive approach for Full AdaGrad and its streaming version, with reduced computational costs. For all the new estimators we propose, we establish their convergence rates as well as their asymptotic efficiency. Moreover, we illustrate the efficiency of these algorithms using numerical simulations and by applying them to real data

APA, Harvard, Vancouver, ISO, and other styles

2

Robert, Philippe. "Réseaux Stochastiques et Algorithmes." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2006. http://tel.archives-ouvertes.fr/tel-00166813.

Full text

Abstract:

Ce document présente plusieurs méthodes de renormalisation utilisées dans l'étude des réseaux stochastiques. En premier lieu il s'agit d'analyser les limites de processus markoviens de sauts renormalisés en temps et en espace suivant une échelle d'Euler (type loi fonctionnelle des grands nombres). Plusieurs aspects sont détaillés: la question des limites non déterministe et ses conséquences, ainsi que le cas de la dimension infinie intervenant pour les processus de Markov à valeurs dans
les chaînes de caractères. L'étude des réseaux avec un grand nombre de noeuds (limite thermodynamique) ou avec des liens de capacité très grandes (Régime limite de Kelly) est discuté ainsi que les perspectives de ce type d'étude.
L'étude mathématique de plusieurs algorithmes distribués gérant des réseaux stochastiques est présentée. L'accent est mis sur les méthodes probabilistes utilisées dans un contexte qui n'est pas nécessairement probabiliste, elles permettent notamment d'étendre et de simplifier une partie des résultats connus dans ce domaine.

APA, Harvard, Vancouver, ISO, and other styles

3

Aguech, Rafik. "Algorithmes stochastiques : etude asymptotique de l'erreur." Paris 6, 2000. http://www.theses.fr/2000PA066004.

Full text

Abstract:

Cette these est composee de deux parties representant les etudes asymptotiques pour les deux classes d'algorithmes stochastiques (a pas decroissant et a pas constant). La premiere partie contient une etude asymptotique de second ordre des algorithmes stochastiques a pas decroissant et une comparaison des trois algorithmes : de newton, des moindres carres et de polyak (la moyennisation). La seconde partie presente des resultats sur les developpements en perturbations des algorithmes de poursuite a pas constant.

APA, Harvard, Vancouver, ISO, and other styles

4

Arouna, Bouhari. "Méthodes de Monté Carlo et algorithmes stochastiques." Marne-la-vallée, ENPC, 2004. https://pastel.archives-ouvertes.fr/pastel-00001269.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

PELLETIER, MARIANE. "Sur le comportement asymptotique des algorithmes stochastiques." Paris 11, 1996. http://www.theses.fr/1996PA112380.

Full text

Abstract:

Cette these est consacree a l'etude des vitesses de convergence en loi et presque sures des algorithmes stochastiques a pas decroissants utilises pour la recherche des zeros (ou des minima) d'une fonction. Dans le premier chapitre, on etablit la vitesse de convergence en loi d'un algorithme faiblement excite conditionnellement a l'ensemble des trajectoires qui convergent vers une cible attractive, ainsi que la vitesse de convergence en loi des algorithmes de recuit simule. Les chapitres deux et trois concernent les proprietes presque sures des algorithmes faiblement excites (loi du logarithme itere, loi forte quadratique des grands nombres et theoreme de limite centrale presque sure). On montre dans le quatrieme chapitre que la methode de moyennisation des algorithmes, connue pour permettre la construction d'algorithmes asymptotiquement efficaces, permet egalement d'obtenir des algorithmes presque surement asymptotiquement efficaces. Enfin le cinquieme chapitre est consacre a l'etude des vitesses de convergence des estimateurs des moindres carres et du gradient pour les modeles lineaires. En particulier, un nouvel estimateur, calculable plus facilement que l'estimateur des moindres carres et possedant les memes proprietes asymptotiques optimales que ce dernier, est propose dans le cas des modeles ar(p)

APA, Harvard, Vancouver, ISO, and other styles

6

Touijar, Driss. "Algorithmes stochastiques et application à l'imagerie électromagnétique baysienne." Lille 1, 1994. http://www.theses.fr/1994LIL10123.

Full text

Abstract:

Ce travail comporte deux aspects: theorique et pratique. L'aspect theorique consiste a etudier certains algorithmes stochastiques utilisables dans les techniques bayesiennes d'inversion. L'aspect pratique consiste a mettre en uvre ces algorithmes pour resoudre un probleme inverse en geomagnetisme. Le premier chapitre traite le probleme inverse dans le cas d'une plaque mince heterogene dans le sous-sol. Autrement dit, le probleme pose est d'essayer de retrouver les valeurs des conductances de cette plaque horizontale a l'aide des mesures de champs electrique et magnetique effectuees a la surface du sol. Dans le deuxieme chapitre, on utilise la methode de l'o. D. E. (ordinary differential equation) pour etudier des proprietes d'un algorithme utilise dans le premier chapitre. Dans le troisieme chapitre, on etudie la stabilite de cet algorithme a l'aide d'une methode de contraction. On trouve des conditions sous lesquelles l'algorithme converge. Le quatrieme chapitre traite le probleme inverse dans le cas d'une coupe verticale du terrain dont les resistivites ne varient que suivant les deux directions horizontale et verticale.

APA, Harvard, Vancouver, ISO, and other styles

7

Krueger, Martin. "Méthode d'analyse d'algorithmes d'optimisation stochastiques à l'aide d'algorithmes génétiques /." Paris : École nationale supérieure des télécommunications, 1994. http://catalogue.bnf.fr/ark:/12148/cb35707870b.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Monmarché, Pierre. "Hypocoercivité : approches alternatives et applications aux algorithmes stochastiques." Toulouse 3, 2014. http://thesesups.ups-tlse.fr/2615/.

Full text

Abstract:

Dans cette thèse, des dynamiques markoviennes alternatives à la diffusion réversible usuelle sont considérées pour échantillonner une mesure de Gibbs dans le cadre d'un algorithme de recuit simulé. Le problème de la convergence, à température fixée, de ces processus vers leur mesure invariante amène à des questions d'hypocoercivité. Dans la mesure où les résultats antérieurs dans le domaine ne donnent pas d'asymptotiques précises du taux de convergence à basse température, de nouvelles méthodes pour obtenir de tels taux explicites sont proposées et étudiées, notamment sur les processus de Markov déterministes par morceaux. Enfin une condition optimale sur le schéma de température d'un recuit simulé basé sur le RTP complètement dégénéré est obtenue en dimension un
Some Markov dynamics are considered to sample Gibbs laws in the framework of the simulated annealing algorithm, as possible alternatives to the usual reversible diffusion. The problem of the convergence, at fixed temperature, of these processes toward their equilibrium leads to hypococercivity questions. Since the previous results in this field do not yield sharp asymptotics for the convergence rate at low temperature, new methods are investigated, in particular in the case of piecewise deterministic Markov processes. Finally an optimal condition is given for the cooling

APA, Harvard, Vancouver, ISO, and other styles

9

Rochet, Sophie. "Convergence des algorithmes génétiques : modèles stochastiques et épistasie." Aix-Marseille 1, 1998. http://www.theses.fr/1998AIX11032.

Full text

Abstract:

Les algorithmes genetiques sont des algorithmes evolutifs introduits par john holland dans les annees 70. Ils sont utilises pour resoudre les problemes d'optimisation. Le travail realise dans cette these se concentre autour de l'idee de convergence dans ces algorithmes sur le plan theorique et pratique. Tout d'abord, deux modeles sont elabores dans le but d'acceder a une demonstration purement mathematique d'un theoreme enonce par holland, le theoreme des schemas, concernant les structures preservees lors d'un cycle de l'algorithme genetique. En ce qui concerne l'action de la selection, il faut utiliser les distributions de bernoulli afin d'arriver a un resultat en accord avec celui de holland. Le meme modele n'etant pas exploitable pour les autres operateurs, un modele dynamique plus classique est construit a l'aide des chaines de markov. Ce modele est utilise afin d'approcher le theoreme des schemas sous un autre angle, en utilisant une generalisation de la notion de schema. L'aspect pratique de la convergence est aussi etudie a l'aide d'un outil introduit par davidor : l'epistasie. La definition de celle-ci etant assez obscure au depart, une analyse en detail a ete faite, grace a une decomposition dans la base de walsh. Ce travail met en lumiere la signification profonde de l'epistasie et sa relation etroite avec une approximation lineaire. A l'aide des resultat theoriques demontres, qui permettent de calculer l'epistasie de maniere acceleree, une campagne de tests a ete menee sur divers aspects de la convergence et de la difficulte d'un probleme pour l'algorithme genetique. Une etude sur le choix de l'estimateur de l'epistasie permet de mettre en evidence l'importance des resultats obtenus pour une estimation efficace. Enfin, les relations entre epistasie et performance de l'operateur de croisement sont mises en lumiere.

APA, Harvard, Vancouver, ISO, and other styles

10

PREVOST, DONALD. "Retines artificielles stochastiques : algorithmes et mise en uvre." Paris 11, 1995. http://www.theses.fr/1995PA112505.

Full text

Abstract:

Cette these traite de problemes de vision bas-niveau, lesquels entrent dans la classe des problemes inverses mal-poses au sens mathematique. Leur resolution est envisagee sous l'angle de l'approche bayesienne sur champ de markov. Specifiquement, nous etudions les algorithmes d'optimisation applicables a des fonctions d'energie semi-quadratiques, telles que rencontrees en vision bas-niveau (detection de contours, segmentation des textures, determination de mouvement ou stereovision). Ces energies sont definies sur un champ de markov couple. Notre premier objectif est de determiner des approches algorithmiques avantageuses selon les criteres de l'optimalite de la solution ; de la qualite de la restauration, des perspectives de parallelisation et de realisation materielle. Notre demarche consiste a considerer une tache simple: la restauration d'images avec prise en compte des discontinuites. Nous avons compare differents algorithmes dedies a cette tache, puis nous avons propose une methode stochastique, simple et parallelisable, que nous avons appelee relaxation quasi-statique (rqs). Le second objectif releve de l'implantation materielle optoelectronique. Nous proposons une architecture parallele de mise en uvre pour l'algorithme rqs. Celle-ci reflete la structure du champ de markov couple: elle est base sur l'operation conjuguee d'un reseau de resistance stochastique et d'un module binaire. Afin de demontrer la faisabilite de machines d'optimisation stochastique operant a cadence video, nous avons concu et teste un systeme realisant des calculs de monte-carlo sur le probleme du verre de spin. Ce systeme utilise un circuit integre cmos optoelectronique (collaboration avec l'ief, contrat dret n 92-139) et un generateur optique de figures de speckle

APA, Harvard, Vancouver, ISO, and other styles

11

Godichon-Baggioni, Antoine. "Algorithmes stochastiques pour la statistique robuste en grande dimension." Thesis, Dijon, 2016. http://www.theses.fr/2016DIJOS053/document.

Full text

Abstract:

Cette thèse porte sur l'étude d'algorithmes stochastiques en grande dimension ainsi qu'à leur application en statistique robuste. Dans la suite, l'expression grande dimension pourra aussi bien signifier que la taille des échantillons étudiés est grande ou encore que les variables considérées sont à valeurs dans des espaces de grande dimension (pas nécessairement finie). Afin d'analyser ce type de données, il peut être avantageux de considérer des algorithmes qui soient rapides, qui ne nécessitent pas de stocker toutes les données, et qui permettent de mettre à jour facilement les estimations. Dans de grandes masses de données en grande dimension, la détection automatique de points atypiques est souvent délicate. Cependant, ces points, même s'ils sont peu nombreux, peuvent fortement perturber des indicateurs simples tels que la moyenne ou la covariance. On va se concentrer sur des estimateurs robustes, qui ne sont pas trop sensibles aux données atypiques. Dans une première partie, on s'intéresse à l'estimation récursive de la médiane géométrique, un indicateur de position robuste, et qui peut donc être préférée à la moyenne lorsqu'une partie des données étudiées est contaminée. Pour cela, on introduit un algorithme de Robbins-Monro ainsi que sa version moyennée, avant de construire des boules de confiance non asymptotiques et d'exhiber leurs vitesses de convergence $L^{p}$ et presque sûre.La deuxième partie traite de l'estimation de la "Median Covariation Matrix" (MCM), qui est un indicateur de dispersion robuste lié à la médiane, et qui, si la variable étudiée suit une loi symétrique, a les mêmes sous-espaces propres que la matrice de variance-covariance. Ces dernières propriétés rendent l'étude de la MCM particulièrement intéressante pour l'Analyse en Composantes Principales Robuste. On va donc introduire un algorithme itératif qui permet d'estimer simultanément la médiane géométrique et la MCM ainsi que les $q$ principaux vecteurs propres de cette dernière. On donne, dans un premier temps, la forte consistance des estimateurs de la MCM avant d'exhiber les vitesses de convergence en moyenne quadratique.Dans une troisième partie, en s'inspirant du travail effectué sur les estimateurs de la médiane et de la "Median Covariation Matrix", on exhibe les vitesses de convergence presque sûre et $L^{p}$ des algorithmes de gradient stochastiques et de leur version moyennée dans des espaces de Hilbert, avec des hypothèses moins restrictives que celles présentes dans la littérature. On présente alors deux applications en statistique robuste: estimation de quantiles géométriques et régression logistique robuste.Dans la dernière partie, on cherche à ajuster une sphère sur un nuage de points répartis autour d'une sphère complète où tronquée. Plus précisément, on considère une variable aléatoire ayant une distribution sphérique tronquée, et on cherche à estimer son centre ainsi que son rayon. Pour ce faire, on introduit un algorithme de gradient stochastique projeté et son moyenné. Sous des hypothèses raisonnables, on établit leurs vitesses de convergence en moyenne quadratique ainsi que la normalité asymptotique de l'algorithme moyenné
This thesis focus on stochastic algorithms in high dimension as well as their application in robust statistics. In what follows, the expression high dimension may be used when the the size of the studied sample is large or when the variables we consider take values in high dimensional spaces (not necessarily finite). In order to analyze these kind of data, it can be interesting to consider algorithms which are fast, which do not need to store all the data, and which allow to update easily the estimates. In large sample of high dimensional data, outliers detection is often complicated. Nevertheless, these outliers, even if they are not many, can strongly disturb simple indicators like the mean and the covariance. We will focus on robust estimates, which are not too much sensitive to outliers.In a first part, we are interested in the recursive estimation of the geometric median, which is a robust indicator of location which can so be preferred to the mean when a part of the studied data is contaminated. For this purpose, we introduce a Robbins-Monro algorithm as well as its averaged version, before building non asymptotic confidence balls for these estimates, and exhibiting their $L^{p}$ and almost sure rates of convergence.In a second part, we focus on the estimation of the Median Covariation Matrix (MCM), which is a robust dispersion indicator linked to the geometric median. Furthermore, if the studied variable has a symmetric law, this indicator has the same eigenvectors as the covariance matrix. This last property represent a real interest to study the MCM, especially for Robust Principal Component Analysis. We so introduce a recursive algorithm which enables us to estimate simultaneously the geometric median, the MCM, and its $q$ main eigenvectors. We give, in a first time, the strong consistency of the estimators of the MCM, before exhibiting their rates of convergence in quadratic mean.In a third part, in the light of the work on the estimates of the median and of the Median Covariation Matrix, we exhibit the almost sure and $L^{p}$ rates of convergence of averaged stochastic gradient algorithms in Hilbert spaces, with less restrictive assumptions than in the literature. Then, two applications in robust statistics are given: estimation of the geometric quantiles and application in robust logistic regression.In the last part, we aim to fit a sphere on a noisy points cloud spread around a complete or truncated sphere. More precisely, we consider a random variable with a truncated spherical distribution, and we want to estimate its center as well as its radius. In this aim, we introduce a projected stochastic gradient algorithm and its averaged version. We establish the strong consistency of these estimators as well as their rates of convergence in quadratic mean. Finally, the asymptotic normality of the averaged algorithm is given

APA, Harvard, Vancouver, ISO, and other styles

12

Tarrès, Pierre. "Pièges des algorithmes stochastiques et marches aléatoires renforcées par sommets." Cachan, Ecole normale supérieure, 2001. http://www.theses.fr/2001DENS0026.

Full text

Abstract:

La première partie de cette thèse est consacrée aux algorithmes stochastiques. Nous présentons de nouveaux résultats de convergence et de non convergence vers certains ensembles instables du système dynamique associe. Nous étudions, en collaboration avec m. Benaim et s. Schreiber, la modélisation de dynamiques génétiques par des processus d'urnes de polya generalisees. La deuxième partie est consacrée a une conjecture de pemantle et volkov énonçant que les marches aléatoires renforcées par sommets sur les entiers restent p. S. Bloquées dans cinq points au bout d'un certain temps. Nous prouvons cette conjecture, et donnons une nouvelle preuve des résultats obtenus précédemment sur le sujet par pemantle et volkov, en utilisant en partie certaines des techniques mises en oeuvre pour la conjecture.

APA, Harvard, Vancouver, ISO, and other styles

13

Saadane, Sofiane. "Algorithmes stochastiques pour l'apprentissage, l'optimisation et l'approximation du régime stationnaire." Thesis, Toulouse 3, 2016. http://www.theses.fr/2016TOU30203/document.

Full text

Abstract:

Dans cette thèse, nous étudions des thématiques autour des algorithmes stochastiques et c'est pour cette raison que nous débuterons ce manuscrit par des éléments généraux sur ces algorithmes en donnant des résultats historiques pour poser les bases de nos travaux. Ensuite, nous étudierons un algorithme de bandit issu des travaux de N arendra et Shapiro dont l'objectif est de déterminer parmi un choix de plusieurs sources laquelle profite le plus à l'utilisateur en évitant toutefois de passer trop de temps à tester celles qui sont moins performantes. Notre but est dans un premier temps de comprendre les faiblesses structurelles de cet algorithme pour ensuite proposer une procédure optimale pour une quantité qui mesure les performances d'un algorithme de bandit, le regret. Dans nos résultats, nous proposerons un algorithme appelé NS sur-pénalisé qui permet d'obtenir une borne de regret optimale au sens minimax au travers d'une étude fine de l'algorithme stochastique sous-jacent à cette procédure. Un second travail sera de donner des vitesses de convergence pour le processus apparaissant dans l'étude de la convergence en loi de l'algorithme NS sur-pénalisé. La particularité de l'algorithme est qu'il ne converge pas en loi vers une diffusion comme la plupart des algorithmes stochastiques mais vers un processus à sauts non-diffusif ce qui rend l'étude de la convergence à l'équilibre plus technique. Nous emploierons une technique de couplage afin d'étudier cette convergence. Le second travail de cette thèse s'inscrit dans le cadre de l'optimisation d'une fonction au moyen d'un algorithme stochastique. Nous étudierons une version stochastique de l'algorithme déterministe de boule pesante avec amortissement. La particularité de cet algorithme est d'être articulé autour d'une dynamique qui utilise une moyennisation sur tout le passé de sa trajectoire. La procédure fait appelle à une fonction dite de mémoire qui, selon les formes qu'elle prend, offre des comportements intéressants. Dans notre étude, nous verrons que deux types de mémoire sont pertinents : les mémoires exponentielles et polynomiales. Nous établirons pour commencer des résultats de convergence dans le cas général où la fonction à minimiser est non-convexe. Dans le cas de fonctions fortement convexes, nous obtenons des vitesses de convergence optimales en un sens que nous définirons. Enfin, l'étude se termine par un résultat de convergence en loi du processus après une bonne renormalisation. La troisième partie s'articule autour des algorithmes de McKean-Vlasov qui furent introduit par Anatoly Vlasov et étudié, pour la première fois, par Henry McKean dans l'optique de la modélisation de la loi de distribution du plasma. Notre objectif est de proposer un algorithme stochastique capable d'approcher la mesure invariante du processus. Les méthodes pour approcher une mesure invariante sont connues dans le cas des diffusions et de certains autre processus mais ici la particularité du processus de McKean-Vlasov est de ne pas être une diffusion linéaire. En effet, le processus a de la mémoire comme les processus de boule pesante. De ce fait, il nous faudra développer une méthode alternative pour contourner ce problème. Nous aurons besoin d'introduire la notion de pseudo-trajectoires afin de proposer une procédure efficace
In this thesis, we are studying severa! stochastic algorithms with different purposes and this is why we will start this manuscript by giving historicals results to define the framework of our work. Then, we will study a bandit algorithm due to the work of Narendra and Shapiro whose objectif was to determine among a choice of severa! sources which one is the most profitable without spending too much times on the wrong orres. Our goal is to understand the weakness of this algorithm in order to propose an optimal procedure for a quantity measuring the performance of a bandit algorithm, the regret. In our results, we will propose an algorithm called NS over-penalized which allows to obtain a minimax regret bound. A second work will be to understand the convergence in law of this process. The particularity of the algorith is that it converges in law toward a non-diffusive process which makes the study more intricate than the standard case. We will use coupling techniques to study this process and propose rates of convergence. The second work of this thesis falls in the scope of optimization of a function using a stochastic algorithm. We will study a stochastic version of the so-called heavy bali method with friction. The particularity of the algorithm is that its dynamics is based on the ali past of the trajectory. The procedure relies on a memory term which dictates the behavior of the procedure by the form it takes. In our framework, two types of memory will investigated : polynomial and exponential. We will start with general convergence results in the non-convex case. In the case of strongly convex functions, we will provide upper-bounds for the rate of convergence. Finally, a convergence in law result is given in the case of exponential memory. The third part is about the McKean-Vlasov equations which were first introduced by Anatoly Vlasov and first studied by Henry McKean in order to mode! the distribution function of plasma. Our objective is to propose a stochastic algorithm to approach the invariant distribution of the McKean Vlasov equation. Methods in the case of diffusion processes (and sorne more general pro cesses) are known but the particularity of McKean Vlasov process is that it is strongly non-linear. Thus, we will have to develop an alternative approach. We will introduce the notion of asymptotic pseudotrajectory in odrer to get an efficient procedure

APA, Harvard, Vancouver, ISO, and other styles

14

LADELLI, LUCIA. "Theoremes limites pour les chaines de markov : application aux algorithmes stochastiques." Paris 6, 1989. http://www.theses.fr/1989PA066283.

Full text

Abstract:

Cette these se compose de quatre articles et d'une note aux comptes rendus de l'academie des sciences concernant d'une part l'etude du comportement d'une classe d'algorithmes stochastiques, d'autre part un theoreme central limite pour des processus stochastiques markoviens intervenant dans certains problemes de statistique. En ce qui concerne les algorithmes, l'interet est centre sur les algorithmes adaptatifs a dynamique markovienne et les resultats obtenus se situent dans la lignee des travaux effectues par a. Benveniste, m. Metivier et p. Priouret. En ce qui concerne le comportement asymptotique des chaines de markov, dans les modeles que nous avons etudies nous obtenons: dans le cas ergodique, la normalite asymptotique, dans le cas recurrent nul, un processus limite qui est un mouvement brownien change de temps par un processus de mittag-leffler independant du brownien

APA, Harvard, Vancouver, ISO, and other styles

15

Chèze, Guillaume. "Des méthodes symboliques-numériques et exactes pour la factorisation absolue des polynômes en deux variables." Nice, 2004. http://www.theses.fr/2004NICE4092.

Full text

Abstract:

Cette thèse porte sur les algorithmes de factorisation absolue. Elle débute par un état de l'art (avant notre travail) puis présente nos contributions. Celles-ci sont organisées en deux parties. La première partie correspond à l'étude symbolique-numérique. Nous donnons une méthode permettant d'obtenir une factorisation absolue exacte à partir d'une factorisation absolue approchée. Ensuite cette méthode est utilisée pour obtenir un algorithme de factorisation absolue. Cet algorithme reprend des idées développées par A. Galligo, D. Rupprecht, et, M. An Hoeij. Grâce à l'utilisation de l'algorithme LLL, notre algorithme permet d'obtenir la factorisation absolue de polynômes de grands degrés (supérieur à 100) jusqu'ici impossible. La deuxième partie présente deux algorithmes symboliques. Le premier est l'adaptation de la technique ``remonter-recombiner'' à l'algorithme de S. Gao. Nous obtenons ainsi un algorithme de factorisation absolue ayant une meilleure complexité que celui de S. Gao. Le deuxième est un algorithme, de type Las Vegas, qui nous permet de tester l'irréductibilité absolue d'un polynôme à coefficients entiers. L'approche proposée tire profit du calcul modulaire et de l'information contenu dans le polytope de Newton
This thesis is about absolute factorization algorithms. The first chapter is a survey on this topic, and then we describe our contributions. They are divided in two parts. The first part corresponds to the symbolic-numeric study. We give a method which allows us to get an exact absolute factorization from an approximate one. Next, this method is used to get an absolute polynomial factorization algorithm. This algorithm uses ideas developped by A. Galligo, D. Rupprecht, and M. Van Hoeij. Thanks to the LLL algorithm, it allows us to get the absolute factorization for polynomials with big degree (bigger than 100). It was impossible before. In the second part, we give two algorithms. The first one adapt a "lifting and recombination'' scheme to the Gao's algorithm. We get then a new algorithm with a better complexity than the Gao's one. The second one is a Las Vegas algorithm. It is an absolute irreducibility test for polynomials with integer coefficients. This algorithm use modular computations, and the shape of the Newton's polytope

APA, Harvard, Vancouver, ISO, and other styles

16

Lelong, Jérôme. "Étude asymptotique des algorithmes stochastiques et calcul du prix des options parisiennes." Phd thesis, Ecole des Ponts ParisTech, 2007. http://pastel.archives-ouvertes.fr/pastel-00003310.

Full text

Abstract:

Cette thèse traite de deux sujets indépendants. La première partie est consacrée à l'étude des algorithmes stochastiques. Dans un premier chapitre introductif, je présente l'algorithme de [55] dans un parallèle avec l'algorithme de Newton pour l'optimisation déterministe. Ces quelques rappels permettent alors d'introduire les algorithmes stochastiques aléatoirement tronqués de [21] qui sont au cœur de cette thèse. La première étude de cet algorithme concerne sa convergence presque sûre qui est parfois établie sous des hypothèses assez changeantes. Ce premier chapitre est l'occasion de clarifier les hypothèses de la convergence presque sûre et d'en présenter une preuve simplifiée. Dans le second chapitre, nous poursuivons l'étude de cet algorithme en nous intéressant cette fois à sa vitesse de convergence. Plus exactement, nous considérons une version moyenne mobile de cet algorithme et démontrons un théorème centrale limite pour cette variante. Le troisième chapitre est consacré à deux applications de ces algorithmes à la finance : le premier exemple présente une méthode de calibration de la corrélation pour les modèles de marchés multidimensionnels alors que le second exemple poursuit les travaux de [7] en améliorant ses résultats. La seconde partie de cette thèse s'intéresse à l'évaluation des options parisiennes en s'appuyant sur les travaux de Chesney, Jeanblanc-Picqué, and Yor [23]. La méthode d'évaluation se base sur l'obtention de formules fermées pour les transformées de Laplace des prix par rapport à la maturité. Nous établissons ces formules pour les options parisiennes simple et double barrières. Nous étudions ensuite une méthode d'inversion numérique de ces transformées. Nous établissons un résultat sur la précision de cette méthode numérique tout à fait performante. A cette occasion, nous démontrons également des résultats liés à la régularité des prix et l'existence d'une densité par rapport à la mesure de Lebesgues pour les temps parisiens.

APA, Harvard, Vancouver, ISO, and other styles

17

Lelong, Jérôme. "Etude asymptotique des algorithmes stochastiques et calcul des prix des options Parisiennes." Phd thesis, Ecole Nationale des Ponts et Chaussées, 2007. http://tel.archives-ouvertes.fr/tel-00201373.

Full text

Abstract:

La première partie de cette thèse est consacrée à l'étude des algorithmes stochastiques aléatoirement tronqués de Chen et Zhu. La première étude de cet algorithme concerne sa convergence presque sûre. Dans le second chapitre, nous poursuivons l'étude de cet algorithme en nous intéressant à sa vitesse de convergence. Nous considérons également une version moyenne mobile de cet algorithme. Enfin nous terminons par quelques applications à la finance.
La seconde partie de cette thèse s'intéresse à l'évaluation des options parisiennes en s'appuyant sur les travaux de Chesney, Jeanblanc et Yor. La méthode d'évaluation se base sur l'obtention de formules fermées pour les transformées de Laplace des prix par rapport à la maturité. Nous établissons ces formules pour les options parisiennes simple et double barrières. Nous étudions ensuite une méthode d'inversion numérique de ces transformées dont nous établissons la précision.

APA, Harvard, Vancouver, ISO, and other styles

18

Peel, Thomas. "Algorithmes de poursuite stochastiques et inégalités de concentration empiriques pour l'apprentissage statistique." Thesis, Aix-Marseille, 2013. http://www.theses.fr/2013AIXM4769/document.

Full text

Abstract:

La première partie de cette thèse introduit de nouveaux algorithmes de décomposition parcimonieuse de signaux. Basés sur Matching Pursuit (MP) ils répondent au problème suivant : comment réduire le temps de calcul de l'étape de sélection de MP, souvent très coûteuse. En réponse, nous sous-échantillonnons le dictionnaire à chaque itération, en lignes et en colonnes. Nous montrons que cette approche fondée théoriquement affiche de bons résultats en pratique. Nous proposons ensuite un algorithme itératif de descente de gradient par blocs de coordonnées pour sélectionner des caractéristiques en classification multi-classes. Celui-ci s'appuie sur l'utilisation de codes correcteurs d'erreurs transformant le problème en un problème de représentation parcimonieuse simultanée de signaux. La deuxième partie expose de nouvelles inégalités de concentration empiriques de type Bernstein. En premier, elles concernent la théorie des U-statistiques et sont utilisées pour élaborer des bornes en généralisation dans le cadre d'algorithmes de ranking. Ces bornes tirent parti d'un estimateur de variance pour lequel nous proposons un algorithme de calcul efficace. Ensuite, nous présentons une version empirique de l'inégalité de type Bernstein proposée par Freedman [1975] pour les martingales. Ici encore, la force de notre borne réside dans l'introduction d'un estimateur de variance calculable à partir des données. Cela nous permet de proposer des bornes en généralisation pour l'ensemble des algorithmes d'apprentissage en ligne améliorant l'état de l'art et ouvrant la porte à une nouvelle famille d'algorithmes d'apprentissage tirant parti de cette information empirique
The first part of this thesis introduces new algorithms for the sparse encoding of signals. Based on Matching Pursuit (MP) they focus on the following problem : how to reduce the computation time of the selection step of MP. As an answer, we sub-sample the dictionary in line and column at each iteration. We show that this theoretically grounded approach has good empirical performances. We then propose a bloc coordinate gradient descent algorithm for feature selection problems in the multiclass classification setting. Thanks to the use of error-correcting output codes, this task can be seen as a simultaneous sparse encoding of signals problem. The second part exposes new empirical Bernstein inequalities. Firstly, they concern the theory of the U-Statistics and are applied in order to design generalization bounds for ranking algorithms. These bounds take advantage of a variance estimator and we propose an efficient algorithm to compute it. Then, we present an empirical version of the Bernstein type inequality for martingales by Freedman [1975]. Again, the strength of our result lies in the variance estimator computable from the data. This allows us to propose generalization bounds for online learning algorithms which improve the state of the art and pave the way to a new family of learning algorithms taking advantage of this empirical information

APA, Harvard, Vancouver, ISO, and other styles

19

Gavra, Iona Alexandra. "Algorithmes stochastiques d'optimisation sous incertitude sur des structures complexes : convergence et applications." Thesis, Toulouse 3, 2017. http://www.theses.fr/2017TOU30141/document.

Full text

Abstract:

Les principaux sujets étudiés dans cette thèse concernent le développement d'algorithmes stochastiques d'optimisation sous incertitude, l'étude de leurs propriétés théoriques et leurs applications. Les algorithmes proposés sont des variantes du recuit simulé qui n'utilisent que des estimations sans biais de la fonction de coût. On étudie leur convergence en utilisant des outils développés dans la théorie des processus de Markov : on utilise les propriétés du générateur infinitésimal et des inégalités fonctionnelles pour mesurer la distance entre leur distribution et une distribution cible. La première partie est dédiée aux graphes quantiques, munis d'une mesure de probabilité sur l'ensemble des sommets. Les graphes quantiques sont des versions continues de graphes pondérés non-orientés. Le point de départ de cette thèse a été de trouver la moyenne de Fréchet de tels graphes. La moyenne de Fréchet est une extension aux espaces métriques de la moyenne euclidienne et est définie comme étant le point qui minimise la somme des carrés des distances pondérées à tous les sommets. Notre méthode est basée sur une formulation de Langevin d'un recuit simulé bruité et utilise une technique d'homogénéisation. Dans le but d'établir la convergence en probabilité du processus, on étudie l'évolution de l'entropie relative de sa loi par rapport a une mesure de Gibbs bien choisie. En utilisant des inégalités fonctionnelles (Poincaré et Sobolev) et le lemme de Gronwall, on montre ensuite que l'entropie relative tend vers zéro. Notre méthode est testée sur des données réelles et nous proposons une méthode heuristique pour adapter l'algorithme à de très grands graphes, en utilisant un clustering préliminaire. Dans le même cadre, on introduit une définition d'analyse en composantes principales pour un graphe quantique. Ceci implique, une fois de plus, un problème d'optimisation stochastique, cette fois-ci sur l'espace des géodésiques du graphe. Nous présentons un algorithme pour trouver la première composante principale et conjecturons la convergence du processus de Markov associé vers l'ensemble voulu. Dans une deuxième partie, on propose une version modifiée de l'algorithme du recuit simulé pour résoudre un problème d'optimisation stochastique global sur un espace d'états fini. Notre approche est inspirée du domaine général des méthodes Monte-Carlo et repose sur une chaine de Markov dont la probabilité de transition à chaque étape est définie à l'aide de " mini-lots " de taille croissante (aléatoire). On montre la convergence en probabilité de l'algorithme vers l'ensemble optimal, on donne la vitesse de convergence et un choix de paramètres optimisés pour assurer un nombre minimal d'évaluations pour une précision donnée et un intervalle de confiance proche de 1. Ce travail est complété par un ensemble de simulations numériques qui illustrent la performance pratique de notre algorithme à la fois sur des fonctions tests et sur des données réelles issues de cas concrets
The main topics of this thesis involve the development of stochastic algorithms for optimization under uncertainty, the study of their theoretical properties and applications. The proposed algorithms are modified versions of simulated an- nealing that use only unbiased estimators of the cost function. We study their convergence using the tools developed in the theory of Markov processes: we use properties of infinitesimal generators and functional inequalities to measure the distance between their probability law and a target one. The first part is concerned with quantum graphs endowed with a probability measure on their vertex set. Quantum graphs are continuous versions of undirected weighted graphs. The starting point of the present work was the question of finding Fréchet means on such a graph. The Fréchet mean is an extension of the Euclidean mean to general metric spaces and is defined as an element that minimizes the sum of weighted square distances to all vertices. Our method relies on a Langevin formulation of a noisy simulated annealing dealt with using homogenization. In order to establish the convergence in probability of the process, we study the evolution of the relative entropy of its law with respect to a convenient Gibbs measure. Using functional inequalities (Poincare and Sobolev) and Gronwall's Lemma, we then show that the relative entropy goes to zero. We test our method on some real data sets and propose an heuristic method to adapt the algorithm to huge graphs, using a preliminary clustering. In the same framework, we introduce a definition of principal component analysis for quantum graphs. This implies, once more, a stochastic optimization problem, this time on the space of the graph's geodesics. We suggest an algorithm for finding the first principal component and conjecture the convergence of the associated Markov process to the wanted set. On the second part, we propose a modified version of the simulated annealing algorithm for solving a stochastic global optimization problem on a finite space. Our approach is inspired by the general field of Monte Carlo methods and relies on a Markov chain whose probability transition at each step is defined with the help of mini batches of increasing (random) size. We prove the algorithm's convergence in probability towards the optimal set, provide convergence rate and its optimized parametrization to ensure a minimal number of evaluations for a given accuracy and a confidence level close to 1. This work is completed with a set of numerical experiments and the assessment of the practical performance both on benchmark test cases and on real world examples

APA, Harvard, Vancouver, ISO, and other styles

20

Le, Coz Mathieu. "Evaluation de performances des algorithmes liés aux télécommunications." Versailles-St Quentin en Yvelines, 2004. http://www.theses.fr/2004VERS0017.

Full text

Abstract:

Une approche classique en évaluation de performances consiste à calculer des indices de performances sur un système donné. Une démarche possible consiste à modéliser le système, calculer sa distribution stationnaire (étape de résolution) et évaluer sur cette distribution les indices de performances souhaités. La résolution consiste à trouver la solution à un système d'équations linéaires de la dimension de l'espace d'états du modèle étudié. La difficultée vient alors de la dimension de ce système qui peut être très élevée (jusqu'à plusieurs dizaines de millions d'états). Le travail de cette thèse consiste à modifier le modèle de manière à ce que la résolution du nouveau modèle soit plus rapide que sur le modèle initial. La première partie de cette thèse consiste à transformer le modèle initial en utilisant des techniques de bornes stochastiques. Il est possible d'imposer, lors du calcul de cette borne, une structure particulière à ce nouveau modèle permettant ainsi une résolution plus rapide. Notamment, l'algorithme LIMSUB calcule une borne agrégée selon une partition des états fixée en utilisant la définition de l'agrégation forte. La seconde traite du formalisme des réseaux d'automates stochastiques (RAS) et montre comment il est possible, sous une contrainte de mémoire donnée, d'effectuer certaines opérations de regroupement d'automates avant l'étape de résolution. Il est également montré que le problème lié au choix des meilleurs regroupements possibles est un problème P-complet. Un algorithme calculant une borne d'un système modélisé par un réseau d'automates stochastiques est ensuite présenté
A classical approach in performance evaluation consists in computing performance indices on a specific system. One may modelise the system, computes the stationnary distribution vector (resolution step) and evaluate the performance indices on this vector. The resolution of the model leads to find the solution of a linear system of equations. The size of this linear system is the size of the model reachable state space. An important difficulty is due to this size since it can be very large (up to several million states). The work of this thesis consists in transforming the initial model so that the resolution of the modified model is faster than the resolution of the initial one. The first part of this thesis consists in transforming the initial model by using techniques of stochastic bounds. During the computation of this bound, we force it to have a particular structure. This structure can be used to reduce time resolution. In particular, algorithm LIMSUB computes a stochastic bound according to a fixed partition of the states by using the definition of strong aggregation. The second part deals with the stochastic automata network (SAN) formalism. It shows how to group automata together before the resolution step. This grouping operation allows to reduce the time resolution of the SAN. The problem of choosing the best possible groups under a given constraint of memory is formulated and is prooved to be an NP-complete problem. An algorithm computing an aggregated bound of a system modelled by a stochastic automata network is then given and some develloped programs are presented

APA, Harvard, Vancouver, ISO, and other styles

21

Naja, Dania. "Convergence d'algorithmes stochastiques : 1-recuit simulé sans potentiel. 2-quelques algorithmes d'auto-organisation." Nancy 1, 1998. http://www.theses.fr/1998NAN10261.

Full text

Abstract:

Cette thèse comporte deux parties différentes : dans la première, nous étudions la convergence des algorithmes stochastiques avec perturbation exogène. Nous distinguons deux vitesses de décroissance de la variance : rapidement décroissante et vitesse du recuit simulé. Le principal résultat est la caractérisation des valeurs d'adhérence en loi du recuit simulé à temps discret pour un bruit exogène gaussien et dont la dérive n'est pas un gradient. Nous étendons ensuite ce résultat au cas d'un bruit exogène non gaussien. La seconde partie est consacrée à l'étude de deux algorithmes d'auto-organisation à bords fixes. Le premier est une généralisation de celui proposé par Cottrell-Fort en 86, le second a été introduit par Flanagan en 94. Nous montrons la convergence en loi de ces deux algorithmes à pas constant en utilisant la méthode de système de particules introduite par Kipnis-Saada en 96. Ensuite, nous montrons que chacun des deux a pas décroissant converge p. S. Vers un équilibre stable de l'O. D. E associée, par application du théorème de Kushner-Clark.

APA, Harvard, Vancouver, ISO, and other styles

22

Huang, Lorick. "EDS dirigées par des processus stables : Méthode paramétrix pour des estimées de densités et application aux algorithmes stochastiques." Sorbonne Paris Cité, 2015. https://theses.hal.science/tel-01180708.

Full text

Abstract:

Premièrement, nous étudions une classe d'équations différentielles stochastiques dirigées par des processus stables (possiblement tempérés), sous des hypothèses de régularité Wilder sur les coefficients. Nous prouvons que le problème de martingale associé est bien posé, établissant ainsi l'unicité faible pour l'EDS. Nous donnons aussi un encadrement de la densité de la solution par celle d'un processus stable (possiblement tempéré). Notre approche est basée sur la méthode parametrix. Dans un second temps, nous considérons une équation différentielle stochastique dégénérée dirigée par un processus stable dont les coefficients satisfont une sorte d'hypothèse de Hôrmander faible. Sous de relativement faibles hypothèses de régularité et des restrictions dimensionnelles, nous prouvons que le problème de martingale est bien posé. Nous donnons également un majorant de la densité reflétant le caractère multi-échelle du processus sous-jacent dans le cas scalaire du stable tempéré. Enfin, nous obtenons un développement pour l'erreur de discrétisation de la cible d'un algorithme stochastique à la suite de [30]. Ceci nous permet de mettre en place une extrapolation de Richardson-Romberg dans le cadre des algorithmes stochastiques, déjà obtenue pour les estimateurs de Monte Carlo linéaires (introduite par Talay et Tubaro [79] et pleinement étudiée dans Pagès [65]) Nous appliquons nos résultats à l'estimation du quantile de la solution d'une EDS dirigée par un processus stable. Les résultats numériques produits à partir de notre méthode montrent une réduction significative de la complexité
Density Estimates for SDEs Driven by Tempered Stable Processes. We study a class of stochastic differential equations driven by a possibly tempered Lévy process, under mild conditions on the coefficients (Wilder continuity). We prove the well-posedness of the associated martingale problem as well as the existence of the density of the solution. Two sided heat kernel estimates are given as well. Our approach is based on the Parametrix series expansion. A Parametrix Approach for some Degenerate Stable Driven SDEs. We consider a stable driven degenerate stochastic differential equation, whose coeffi- cients satisfy a kind of weak Hôrmander condition. Under mild smoothness assumptions we prove the uniqueness of the martingale problem for the associated generator under some dimension constraints. Also, when the driving noise is scalar and tempered, we establish density bounds reflecting the multi-scale behavior of the process. A Multi-step Richardson-Romberg extrapolation method for stochastic approximation We obtain an expansion of the implicit weak discretization error for the target of stochastic approximation algorithms introduced and studied in [30]. This allows us to extend and develop the Richardson-Romberg extrapolation method for Monte Carlo linear estimator (introduced in [79] and deeply studied in [65]) to the framework of stochastic optimization by means of stochastic approximation algorithms. We notably apply the method to the estimation of the quantile of diffusion processes. Numerical results confirm the theoretical analysis and show a significant reduction in the initial computational cost

APA, Harvard, Vancouver, ISO, and other styles

23

Abbas, Boushra. "Méthode de Newton régularisée pour les inclusions monotones structurées : étude des dynamiques et algorithmes associés." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS250/document.

Full text

Abstract:

Cette thèse est consacrée à la recherche des zéros d'un opérateur maximal monotone structuré, à l'aide de systèmes dynamiques dissipatifs continus et discrets. Les solutions sont obtenues comme limites des trajectoires lorsque le temps t tend vers l'infini. On s'intéressera principalement aux dynamiques obtenues par régularisation de type Levenberg-Marquardt de la méthode de Newton. On décrira aussi les approches basées sur des dynamiques voisines.Dans un cadre Hilbertien, on s'intéresse à la recherche des zéros de l'opérateur maximal monotone structuré M = A + B, où A est un opérateur maximal monotone général et B est un opérateur monotone Lipschitzien. Nous introduisons des dynamiques continues et discrètes de type Newton régularisé faisant intervenir d'une façon séparée les résolvantes de l'opérateur A (implicites), et des évaluations de B (explicites). A l'aide de la représentation de Minty de l'opérateur A comme une variété Lipschitzienne, nous reformulons ces dynamiques sous une forme relevant du théorème de Cauchy-Lipschitz. Nous nous intéressons au cas particulier où A est le sous différentiel d'une fonction convexe, semi-continue inférieurement, et propre, et B est le gradient d'une fonction convexe, différentiable. Nous étudions le comportement asymptotique des trajectoires. Lorsque le terme de régularisation ne tend pas trop vite vers zéro, et en s'appuyant sur une analyse asymptotique de type Lyapunov, nous montrons la convergence des trajectoires. Par ailleurs, nous montrons la dépendance Lipschitzienne des trajectoires par rapport au terme de régularisation.Puis nous élargissons notre étude en considérant différentes classes de systèmes dynamiques visant à résoudre les inclusions monotones gouvernées par un opérateur maximal monotone structuré M = $partialPhi$+ B, où $partialPhi$ désigne le sous différentiel d'une fonction convexe, semicontinue inférieurement, et propre, et B est un opérateur monotone cocoercif. En s'appuyant sur une analyse asymptotique de type Lyapunov, nous étudions le comportement asymptotique des trajectoires de ces systèmes. La discrétisation temporelle de ces dynamiques fournit desalgorithmes forward-backward (certains nouveaux ).Finalement, nous nous intéressons à l'étude du comportement asymptotique des trajectoires de systèmes dynamiques de type Newton régularisé, dans lesquels on introduit un terme supplémentaire de viscosité évanescente de type Tikhonov. On obtient ainsi la sélection asymptotique d'une solution de norme minimale
This thesis is devoted to finding zeroes of structured maximal monotone operators, by using discrete and continuous dissipative dynamical systems. The solutions are obtained as the limits of trajectories when the time t tends towards infinity.We pay special attention to the dynamics that are obtained by Levenberg-Marquardt regularization of Newton's method. We also revisit the approaches based on some related dynamical systems.In a Hilbert framework, we are interested in finding zeroes of a structured maximal monotone operator M = A + B, where A is a general maximal monotone operator, and B is monotone and locally Lipschitz continuous. We introduce discrete and continuous dynamical systems which are linked to Newton's method. They involve separately B and the resolvents of A, and are designed to splitting methods. Based on the Minty representation of A as a Lipschitz manifold, we show that these dynamics can be formulated as differential systems, which are relevant to the Cauchy-Lipschitz theorem. We focus on the particular case where A is the subdifferential of a convex lower semicontinuous proper function, and B is the gradient of a convex, continuously differentiable function. We study the asymptotic behavior of trajectories. When the regularization parameter does not tend to zero too rapidly, and by using Lyapunov asymptotic analysis, we show the convergence of trajectories. Besides, we show the Lipschitz continuous dependence of the solution with respect to the regularization term.Then we extend our study by considering various classes of dynamical systems which aim at solving inclusions governed by structured monotone operators M = $partialPhi$+ B, where $partialPhi$ is the subdifferential of a convex lower semicontinuous function, and B is a monotone cocoercive operator. By a Lyapunov analysis, we show the convergence properties of the orbits of these systems. The time discretization of these dynamics gives various forward-backward splittingmethods (some new).Finally, we focus on the study of the asymptotic behavior of trajectories of the regularized Newton dynamics, in which we introduce an additional vanishing Tikhonov-like viscosity term.We thus obtain the asymptotic selection of the solution of minimal norm

APA, Harvard, Vancouver, ISO, and other styles

24

Nsiri, Saïd. "L'utilisation des représentations markoviennes dans l'identification des processus stochastiques ARMA vectoriels." Paris 7, 1985. http://www.theses.fr/1985PA07F134.

Full text

Abstract:

On a souligné dans ce travail l'intérêt de l'utilisation des représentations markoviennes dans l'étude des processus stochastiques ARMA et on a étudié une procédure d'identification de ces processus basée sur l'application d'un algorithme de réalisation matricielle. Cet algorithme, à l'inverse de celui de Ho, s'applique à des variables aléatoires matricielles dont les éléments se distribuent asymptôtiquement selon une loi normale. . . .

APA, Harvard, Vancouver, ISO, and other styles

25

Mesghouni, Khaled. "Application des algorithmes évolutionnistes dans les problèmes d'optimisation en ordonnancement de la production." Lille 1, 1999. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1999/50376-1999-19.pdf.

Full text

Abstract:

Le problème d'ordonnancement des ateliers constitue sûrement pour les entreprises une des difficultés importantes de leur système de gestion et de conduite. En effet, c'est à ce niveau que doivent être prises en compte les caractéristiques réelles multiples et complexes des ateliers. Nous nous intéresserons dans ce travail aux problèmes d'ordonnancement de type job-shop flexible, ce sont des problèmes extrêmement difficiles à résoudre, ils appartiennent à la classe dite NP difficile, ils demandent un espace de recherche combinatoire et un traitement particulièrement complexe. Les méthodes exactes demandent un temps d'exécution considérable et/ou des formulations mathématiques complexes, particulièrement quand la taille du problème est importante. Toutefois, il existe des méthodes dites stochastiques telles que les algorithmes évolutionnistes qui donnent des résultats très proches de l'optimum. Nous proposons deux approches évolutionnistes originales pour résoudre les problèmes du type job-shop flexible. Ces derniers sont sujets à des contraintes diverses qu'il faut absolument respecter pour aboutir à une solution réalisable. La première approche est basée sur le premier codage dit codage parallèle des machines, le chromosome ainsi représente donne une information visible de la charge des machines et de la répartition des opérations sur ces dernières ce qui permet une utilisation efficace du parc de machines. L'utilisation des algorithmes à stratégie d'évolution passe par la mise au point d'une population de démarrage dite population initiale. Vu que cette population conditionne la convergence de notre algorithme, nous avons utilisé un processus hybride utilisant les différentes méthodes classiques pour générer une bonne première population. Dans la deuxième approche, nous proposons un deuxième codage qui intègre la majorité des contraintes du problème d'ordonnancement dans la conception même du chromosome, ceci nous permet de construire des opérateurs de croisement et du mutation sans avoir à intégrer des processus de corrections qui alourdiraient le temps de calcul. Les résultats des simulations que nous avons effectuées montrent bien la validité de nos approches, ainsi que leurs capacités à donner un ensemble de solutions réalisables et proches de l'optimum en un temps très court.

APA, Harvard, Vancouver, ISO, and other styles

26

Stazhynski, Uladzislau. "Discrétisation de processus à des temps d’arrêt et Quantification d'incertitude pour des algorithmes stochastiques." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLX088/document.

Full text

Abstract:

Cette thèse contient deux parties qui étudient deux sujets différents. Les Chapitres 1-4 sont consacrés aux problèmes de discrétisation de processus à des temps d’arrêt. Dans le Chapitre 1 on étudie l'erreur de discrétisation optimale pour des intégrales stochastiques par rapport à une semimartingale brownienne multidimensionnelle continue. Dans ce cadre on établit une borne inférieure trajectorielle pour la variation quadratique renormalisée de l'erreur. On fournit une suite de temps d’arrêt qui donne une discrétisation asymptotiquement optimale. Cette suite est définie comme temps de sortie d'ellipsoïdes aléatoires par la semimartingale. Par rapport aux résultats précédents on permet une classe de semimartingales assez large. On démontre qui la borne inférieure est exacte. Dans le Chapitre 2 on étudie la version adaptative au modèle de la discrétisation optimale d’intégrales stochastique. Dans le Chapitre 1 la construction de la stratégie optimale utilise la connaissance du coefficient de diffusion de la semimartingale considérée. Dans ce travail on établit une stratégie de discrétisation asymptotiquement optimale qui est adaptative au modèle et n'utilise pas aucune information sur le modèle. On démontre l'optimalité pour une classe de grilles de discrétisation assez générale basée sur les technique de noyau pour l'estimation adaptative. Dans le Chapitre 3 on étudie la convergence en loi des erreurs de discrétisation renormalisées de processus d’Itô pour une classe concrète et assez générale de grilles de discrétisation données par des temps d’arrêt. Les travaux précédents sur le sujet considèrent seulement le cas de dimension 1. En plus ils concentrent sur des cas particuliers des grilles, ou démontrent des résultats sous des hypothèses abstraites. Dans notre travail on donne explicitement la distribution limite sous une forme claire et simple, les résultats sont démontré dans le cas multidimensionnel pour le processus et pour l'erreur de discrétisation. Dans le Chapitre 4 on étudie le problème d'estimation paramétrique pour des processus de diffusion basée sur des observations à temps d’arrêt. Les travaux précédents sur le sujet considèrent que des temps d'observation déterministes, fortement prévisibles ou aléatoires indépendants du processus. Sous des hypothèses faibles on construit une suite d'estimateurs consistante pour une classe large de grilles d'observation données par des temps d’arrêt. On effectue une analyse asymptotique de l'erreur d'estimation. En outre, dans le cas du paramètre de dimension 1, pour toute suite d'estimateurs qui vérifie un TCL sans biais, on démontre une borne inférieure uniforme pour la variance asymptotique; on montre que cette borne est exacte. Les Chapitres 5-6 sont consacrés au problème de quantification d'incertitude pour des limites d'approximation stochastique. Dans le Chapitre 5 on analyse la quantification d'incertitude pour des limites d'approximation stochastique (SA). Dans notre cadre la limite est définie comme un zéro d'une fonction donnée par une espérance. Cette espérance est prise par rapport à une variable aléatoire pour laquelle le modèle est supposé de dépendre d'un paramètre incertain. On considère la limite de SA comme une fonction de cette paramètre. On introduit un algorithme qui s'appelle USA (Uncertainty for SA). C'est une procédure en dimension croissante pour calculer les coefficients de base d'expansion de chaos de cette fonction dans une base d'un espace de Hilbert bien choisi. La convergence de USA dans cet espace de Hilbert est démontré. Dans le Chapitre 6 on analyse le taux de convergence dans L2 de l'algorithme USA développé dans le Chapitre 5. L'analyse est non trivial à cause de la dimension infinie de la procédure. Le taux obtenu dépend du modèle et des paramètres utilisés dans l'algorithme USA. Sa connaissance permet d'optimiser la vitesse de croissance de la dimension dans USA
This thesis consists of two parts which study two separate subjects. Chapters 1-4 are devoted to the problem of processes discretization at stopping times. In Chapter 1 we study the optimal discretization error of stochastic integrals, driven by a multidimensional continuous Brownian semimartingale. In this setting we establish a path wise lower bound for the renormalized quadratic variation of the error and we provide a sequence of discretization stopping times, which is asymptotically optimal. The latter is defined as hitting times of random ellipsoids by the semimartingale at hand. In comparison with previous available results, we allow a quite large class of semimartingales and we prove that the asymptotic lower bound is attainable. In Chapter 2 we study the model-adaptive optimal discretization error of stochastic integrals. In Chapter 1 the construction of the optimal strategy involved the knowledge about the diffusion coefficient of the semimartingale under study. In this work we provide a model-adaptive asymptotically optimal discretization strategy that does not require any prior knowledge about the model. In Chapter 3 we study the convergence in distribution of renormalized discretization errors of Ito processes for a concrete general class of random discretization grids given by stopping times. Previous works on the subject only treat the case of dimension 1. Moreover they either focus on particular cases of grids, or provide results under quite abstract assumptions with implicitly specified limit distribution. At the contrast we provide explicitly the limit distribution in a tractable form in terms of the underlying model. The results hold both for multidimensional processes and general multidimensional error terms. In Chapter 4 we study the problem of parametric inference for diffusions based on observations at random stopping times. We work in the asymptotic framework of high frequency data over a fixed horizon. Previous works on the subject consider only deterministic, strongly predictable or random, independent of the process, observation times, and do not cover our setting. Under mild assumptions we construct a consistent sequence of estimators, for a large class of stopping time observation grids. Further we carry out the asymptotic analysis of the estimation error and establish a Central Limit Theorem (CLT) with a mixed Gaussian limit. In addition, in the case of a 1-dimensional parameter, for any sequence of estimators verifying CLT conditions without bias, we prove a uniform a.s. lower bound on the asymptotic variance, and show that this bound is sharp. In Chapters 5-6 we study the problem of uncertainty quantification for stochastic approximation limits. In Chapter 5 we analyze the uncertainty quantification for the limit of a Stochastic Approximation (SA) algorithm. In our setup, this limit is defined as the zero of a function given by an expectation. The expectation is taken w.r.t. a random variable for which the model is assumed to depend on an uncertain parameter. We consider the SA limit as a function of this parameter. We introduce the so-called Uncertainty for SA (USA) algorithm, an SA algorithm in increasing dimension for computing the basis coefficients of a chaos expansion of this function on an orthogonal basis of a suitable Hilbert space. The almost-sure and Lp convergences of USA, in the Hilbert space, are established under mild, tractable conditions. In Chapter 6 we analyse the L2-convergence rate of the USA algorithm designed in Chapter 5.The analysis is non-trivial due to infinite dimensionality of the procedure. Moreover, our setting is not covered by the previous works on infinite dimensional SA. The obtained rate depends non-trivially on the model and the design parameters of the algorithm. Its knowledge enables optimization of the dimension growth speed in the USA algorithm, which is the key factor of its efficient performance

APA, Harvard, Vancouver, ISO, and other styles

27

Terrier, Pierre. "Algorithmes stochastiques pour simuler l'évolution microstructurale d'alliages ferritiques : une étude de la dynamique d'amas." Thesis, Paris Est, 2018. http://www.theses.fr/2018PESC1135/document.

Full text

Abstract:

Cette thèse s'intéresse au vieillissement des métaux au niveau microstructural. On étudie en particulier les défauts (amas de lacunes, interstitiels ou solutés) via un modèle de dynamique d'amas (DA), qui permet de prédire l'évolution des concentrations de défauts sur des temps longs (plusieurs dizaines d'années). Ce modèle est décrit par un système d'équations différentielles ordinaires (EDOs) de très grande taille, pouvant excéder la centaine de milliards d'équations. Les méthodes numériques classiques de simulation d'EDOs ne sont alors pas efficaces pour de tels systèmes. On montre dans un premier temps que la DA est bien posée et qu'elle vérifie certaines bonnes propriétés physiques comme la conservation de la quantité de matière et la positivité de la solution. On s'intéresse également à une approximation de la DA, qui prend la forme d'une équation aux dérivées partielles, de type Fokker--Planck. On caractérise en particulier l'erreur d'approximation entre la DA et cette approximation. Dans un second temps, on introduit un algorithme de simulation de la DA. Cet algorithme est basé sur un splitting de la dynamique ainsi que sur une interprétation probabiliste des équations de la DA (sous la forme d'un processus de saut) ou de son approximation de Fokker--Planck (sous la forme d'un processus de Langevin). Le but est de réduire le nombre d'équations à résoudre et d'accélérer par conséquent les simulations. On utilise enfin cet algorithme de simulation à différents modèles physiques. On confirme l'intérêt de ce nouvel algorithme pour des modèles complexes. On montre également que cet algorithme permet d'enrichir le modèle de dynamique d'amas à moindre coût
We study ageing of materials at a microstructural level. In particular, defects such as vacancies, interstitials and solute atoms are described by a model called Cluster Dynamics (CD), which characterize the evolution of the concentrations of such defects, on period of times as long as decades. CD is a set of ordinary differential equations (ODEs), which might contain up to hundred of billions of equations. Therefore, classical methods used for solving system of ODEs are not suited in term of efficiency. We first show that CD is well-posed and that physical properties such as the conservation of matter and the preservation of the sign of the solution are verified. We also study an approximation of CD, namely the Fokker--Planck approximation, which is a partial differential equation. We quantify the error between CD and its approximation. We then introduce an algorithm for simulating CD. The algorithm is based on a splitting of the dynamics and couples a deterministic and a stochastic approach of CD. The stochastic approach interprets directly CD as a jump process or its approximation as a Langevin process. The aim is to reduce the number of equations to solve, hence reducing the computation time. We finally apply this algorithm to physical models. The interest of this approach is validated on complex models. Moreover, we show that CD can be efficiently improved thanks to the versatility of the algorithm

APA, Harvard, Vancouver, ISO, and other styles

28

Huang, Junbo. "Théorème de Berry-Esseen pour martingales normalisées et algorithmes stochastiques : application en contrôle stochastique." Paris 6, 2009. http://www.theses.fr/2009PA066174.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Bouttier, Clément. "Optimisation globale sous incertitude : algorithmes stochastiques et bandits continus avec application aux performances avion." Thesis, Toulouse 3, 2017. http://www.theses.fr/2017TOU30176.

Full text

Abstract:

Cette thèse est consacrée à l'étude théorique et numérique d'algorithmes d'optimisation stochastiques adaptés au traitement du problème de planification des trajectoires d'avions en environnement incertain. L'optimisation des temps de vol et de la consommation de carburant est un élément central de la compétitivité des compagnies aériennes. Elles sont à la recherche d'outils permettant d'optimiser le choix de leurs routes aériennes avec toujours plus de précision. Pourtant, les méthodes actuellement disponibles pour l'optimisation de ces routes aériennes requièrent l'utilisation de représentations simplifiées des performances avion. Nous proposons, dans cette thèse, de répondre à cette exigence de précision et d'adapter, par conséquent, nos méthodes de résolution aux contraintes de la modélisation industrielle des performances avion tout en tenant compte de l'incertitude qui pèse sur les conditions réelles de vol (trafic aérien et conditions atmosphériques). Nous appuyons notre démarche par trois contributions scientifiques. Premièrement, nous avons mis en place un environnement de test pour algorithmes d'optimisation de trajectoires. Ce cadre a permis d'unifier la procédure de test pour l'ensemble des modèles de performances avion. Deuxièmement, nous avons développé et analysé sur le plan théorique deux nouveaux algorithmes d'optimisation stochastique globale en l'absence de dérivés. La première approche, très générique, n'utilise pas d'information particulière liée à la dynamique avion. Il s'agit de l'algorithme NSA basé sur la méthode du recuit simulé. Les développements théoriques ont abouti à la formulation des conditions et vitesse de convergence de cet algorithme. La seconde approche, l'algorithme SPY, est plus spécifique, il utilise une information de régularité lipschitzienne autour de l'optimum recherche. Il s'agit d'un algorithme de type bandits Lipschitz, basé sur la méthode de Piyavskii. De même, nous analysons les conditions de convergence de cet algorithme et fournissons une borne supérieure sur son erreur d'optimisation (regret simple)
This PhD thesis is dedicated to the theoretical and numerical analysis of stochastic algorithms for the stochastic flight planning problem. Optimizing the fuel consumption and flight time is a key factor for airlines to be competitive. These companies thus look for flight optimization tools with higher and higher accuracy requirements. However, nowadays available methodologies for flight planning are based on simplified aircraft performance models. In this PhD, we propose to fulfill the accuracy requirements by adapting our methodology to both the constraints induced by the utilization of an industrial aircraft performance computation code and the consideration of the uncertainty about the real flight conditions, i.e., air traffic and weather conditions. Our proposal is supported by three main contributions. First, we design a numerical framework for benchmarking aircraft trajectory optimization tools. This provides us a unified testing procedure for all aircraft performance models. Second, we propose and study (both theoretically and numerically) two global derivative-free algorithms for stochastic optimization problems. The first approach, the NSA algorithm, is highly generic and does not use any prior knowledge about the aircraft performance model. It is an extension of the simulated annealing algorithm adapted to noisy cost functions. We provide an upper bound on the convergence speed of NSA to globally optimal solutions. The second approach, the SPY algorithm, is a Lipschitz bandit algorithm derived from Piyavskii's algorithm. It is more specific as it requires the knowledge of some Lipschitz regularity property around the optimum, but it is therefore far more efficient. We also provide a theoretical study of this algorithm through an upper bound on its simple regret

APA, Harvard, Vancouver, ISO, and other styles

30

Segalat, Philippe. "Méthodes de points intérieurs et de quasi-Newton." Limoges, 2002. http://www.theses.fr/2002LIMO0041.

Full text

Abstract:

Cette thèse s' intéresse à des méthodes de ponts 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 1-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
This thesis is interested in interior point and quasi-Newton methods in nonlinear optimization and with their implementation. One presents the code NOPTIQ using the limited memory BFGS formulas to solve large scale problems. The originality of this approach is the use of these formulas within the framework of interior point methods. The storage requirement and the computing cost of one iteration are then low. One shows that NOPTIQ is robust and that its performance are comparable with the reference codes 1-BFGS-B and LANCELOT. One presents also an infeasible algorithm using the preceding methods to solve a nonlinear problem with inequality constraints and linear equality constraints. The idea to penalize the problem using shift variables and a variant of the big-M method of linear programming. The q-superlinear convergence of the inner iterates and the global convergence of outer iterates are shown

APA, Harvard, Vancouver, ISO, and other styles

31

Hajji, Omessaad Brochet Pascal. "Contribution au développement de méthodes d'optimisation stochastiques application à la conception des dispositifs électrotechniques /." [S.l.] : [s.n.], 2003. http://www.univ-lille1.fr/bustl-grisemine/pdf/extheses/50376-2003-237-238.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Bossy, Mireille. "Vitesse de convergence d'algorithmes particulaires stochastiques et application à l'équation de Burgers." Aix-Marseille 1, 1995. http://www.theses.fr/1995AIX11007.

Full text

Abstract:

La convergence de la methode de vortex aleatoires pour l'equation de navier-stokes n'a pas encore ete etablie dans un sens pleinement satisfaisant. Ce probleme a fortement motive l'etude d'algorithmes particulaires pour certaines e. D. P. Non lineaires, en particulier, l'equation de burgers que nous presentons dans ce memoire. L'objectif de ce travail est de donner de nouveaux resultats de vitesse de convergence de methodes particulaires stochastiques, a l'aide de l'interpretation probabiliste d'e. D. P non lineaires en terme de systeme de particules en interaction. La theorie des processus stochastiques permet d'interpreter les e. D. P non lineaires de type mckean-vlasov comme des equations limites pour des systemes de particules en interaction. Nous en deduisons un algorithme simple et naturel, fonde sur la simulation du systeme de particules sous-jacent. Nous obtenons la vitesse de convergence de l'algorithme, lorsque les noyaux d'interaction sont lipschitziens et bornes. Nous donnons ensuite une nouvelle interpretation probabiliste de l'equation de burgers en terme de systeme de particules en interaction (le noyau d'interaction correspondant est discontinu) et montrons que le systeme de particules possede la propriete de propagation du chaos. Nous etudions la convergence (theorique et numerique) de l'algorithme. La vitesse de convergence que nous obtenons semble etre ce que l'on peut esperer obtenir pour cette famille d'algorithmes et donne un eclairage theorique nouveau a la methode de vortex aleatoires

APA, Harvard, Vancouver, ISO, and other styles

33

Sidaner, Alain. "Contribution à l'étude de l'algorithme de recherche locale stochastique WalkSAT sur des instances SAT aléatoires." Dijon, 2003. http://www.theses.fr/2003DIJOS044.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Xayaphoummine, Alain. "Simulations et expériences sur le repliement de l'ARN : prédictions statistiques des pseudonœuds in silico et réalisation de commutateurs ARN par transcription in vitro." Université Louis Pasteur (Strasbourg) (1971-2008), 2004. https://publication-theses.unistra.fr/public/theses_doctorat/2004/XAYAPHOUMMINE_Alain_2004.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Tong, Dinh Quy. "Méthodes d'estimation de paramètres de modèles autorégressifs multivariés." Grenoble 1, 1991. http://www.theses.fr/1991GRE10141.

Full text

Abstract:

Cette thèse est consacrée à l'étude des méthodes d'estimation pour un modèle autorégressif multivarié et spécialement à la construction d'algorithmes pour la mise en œuvre de la méthode du maximum de vraisemblance. On présente dans les deux premiers chapitres les différents notions et algorithmes utilisés dans le domaine de l'estimation autorégressive multivariée. On y étudie les aspects algorithmiques de la méthode de Yule-Walker, des méthodes de Burg généralisées, des méthodes basées sur les corrélations partielles. . . La méthode du maximum de vraisemblance est l'objet des trois derniers chapitres. On introduit les différentes façons de calculer la fonction de Log-vraisemblance, ses dérivées premières exactes (par rapport aux différents ensembles de paramètres caractérisant le modèle) et des approximations de ses dérivées secondes. A l'aide de la technique itérative de Newton-Raphson modifiée (méthode itérative de Fisher) on construit ensuite des algorithmes d'optimisation pour le problème d'estimation du maximum de vraisemblance. Les résultats de simulation et les aspects de l'implémentation de ces algorithmes sont également présentés

APA, Harvard, Vancouver, ISO, and other styles

36

Fijany, Amir. "Algorithmes et architectures parallèles en robotique." Paris 11, 1988. http://www.theses.fr/1988PA112258.

Full text

Abstract:

La simulation et le contrôle des mouvements d'un robot manipulateur nécessitent la résolution des problèmes cinématiques et dynamiques. Une capacité de calcul insuffisante a toujours constitué l'obstacle majeur de la simulation et du contrôle en temps réel des mouvements d'un robot manipulateur. Il est unanimement reconnu que l'utilisation d'architectures informatiques parallèles est un facteur clé pour surmonter cet obstacle. L'objectif de ce travail est de déduire les caractéristiques essentielles puis de mettre en oeuvre une architecture hautement parallèle qui procure les améliorations significatives et décisives pour calculer les modèles dynamiques et cinématiques. Pour atteindre cet objectif, nous avons tout d’abord effectué une étude algorithmique puis développé des algorithmes parallèles appropriés et efficaces. Les caractéristiques des architectures informatiques pour la mise en oeuvre de ces algorithmes sont ensuite déterminées en étudiant les propriétés communes des algorithmes. Cette approche a permis d'étudier et de mettre en oeuvre une architecture (MlMD-SlMD) hautement parallèle. Cette architecture a permis d'obtenir une réduction significative du temps de calcul des différents problèmes. Pour un robot à six degrés de liberté, le temps de calcul du modèle dynamique inverse est de 187 micro second tandis que le modèle cinématique et son inverse sont calculés en 75 micro secondes.

APA, Harvard, Vancouver, ISO, and other styles

37

De, Carvalho Gomes Fernando. "Utilisation d'algorithmes stochastiques en apprentissage." Montpellier 2, 1992. http://www.theses.fr/1992MON20254.

Full text

Abstract:

Dans le cadre de l'apprentissage inductif, les données sont souvent mal décrites et bruitées. Dans ce cas, la génération de procédures de classification présentant une parfaite adéquation aux données, produit des résultats de taille (ou complexité) importante. Les performances sont excellentes sur les données ayant servi à apprendre, mais mauvaises sur un ensemble test. On cherche alors des procédures présentant un bon compromis complexité adéquation aux données et la tache se rapproche de l'optimisation. Plusieurs approches gloutonnes ont été proposées. L'objet de cette thèse est de proposer une approche plus puissante. L'apport principal est un algorithme d'apprentissage base sur la recherche stochastique d'une liste de décision de faible complexité. Cet algorithme procède en deux phases distinctes: la diversification et l'intensification de la recherche, exécutées respectivement par le recuit simule et par la méthode tabou

APA, Harvard, Vancouver, ISO, and other styles

38

SEGALAT, Philippe. "Méthodes de Points Intérieurs et de quasi-Newton." Phd thesis, Université de Limoges, 2002. http://tel.archives-ouvertes.fr/tel-00005478.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

39

Reutenauer, Victor. "Algorithmes stochastiques pour la gestion du risque et l'indexation de bases de données de média." Thesis, Université Côte d'Azur (ComUE), 2017. http://www.theses.fr/2017AZUR4018/document.

Full text

Abstract:

Cette thèse s’intéresse à différents problèmes de contrôle et d’optimisation dont il n’existe à ce jour que des solutions approchées. D’une part nous nous intéressons à des techniques visant à réduire ou supprimer les approximations pour obtenir des solutions plus précises voire exactes. D’autre part nous développons de nouvelles méthodes d’approximation pour traiter plus rapidement des problèmes à plus grande échelle. Nous étudions des méthodes numériques de simulation d’équation différentielle stochastique et d’amélioration de calculs d’espérance. Nous mettons en œuvre des techniques de type quantification pour la construction de variables de contrôle ainsi que la méthode de gradient stochastique pour la résolution de problèmes de contrôle stochastique. Nous nous intéressons aussi aux méthodes de clustering liées à la quantification, ainsi qu’à la compression d’information par réseaux neuronaux. Les problèmes étudiés sont issus non seulement de motivations financières, comme le contrôle stochastique pour la couverture d’option en marché incomplet mais aussi du traitement des grandes bases de données de médias communément appelé Big data dans le chapitre 5. Théoriquement, nous proposons différentes majorations de la convergence des méthodes numériques d’une part pour la recherche d’une stratégie optimale de couverture en marché incomplet dans le chapitre 3, d’autre part pour l’extension la technique de Beskos-Roberts de simulation d’équation différentielle dans le chapitre 4. Nous présentons une utilisation originale de la décomposition de Karhunen-Loève pour une réduction de variance de l’estimateur d’espérance dans le chapitre 2
This thesis proposes different problems of stochastic control and optimization that can be solved only thanks approximation. On one hand, we develop methodology aiming to reduce or suppress approximations to obtain more accurate solutions or something exact ones. On another hand we develop new approximation methodology in order to solve quicker larger scale problems. We study numerical methodology to simulated differential equations and enhancement of computation of expectations. We develop quantization methodology to build control variate and gradient stochastic methods to solve stochastic control problems. We are also interested in clustering methods linked to quantization, and principal composant analysis or compression of data thanks neural networks. We study problems motivated by mathematical finance, like stochastic control for the hedging of derivatives in incomplete market but also to manage huge databases of media commonly known as big Data in chapter 5. Theoretically we propose some upper bound for convergence of the numerical method used. This is the case of optimal hedging in incomplete market in chapter 3 but also an extension of Beskos-Roberts methods of exact simulation of stochastic differential equations in chapter 4. We present an original application of karhunen-Loève decomposition for a control variate of computation of expectation in chapter 2

APA, Harvard, Vancouver, ISO, and other styles

40

Arouna, Bouhari. "Algotithmes stochastiques et méthodes de Monte Carlo." Phd thesis, Ecole des Ponts ParisTech, 2004. http://pastel.archives-ouvertes.fr/pastel-00001269.

Full text

Abstract:

Dans cette thèse,nous proposons de nouvelles techniques de réduction de variance, pourles simultions Monté Carlo. Par un simple changement de variable, nous modifions la loi de simulation de façon paramétrique. L'idée consiste ensuite à utiliser une version convenablement projetée des algorithmes de Robbins-Monro pour déterminer le paramètre optimal qui "minimise" la variance de l'estimation. Nous avons d'abord développé une implémentation séquentielle dans laquelle la variance est réduite dynamiquement au cours des itératons Monte Carlo. Enfin, dans la dernière partie de notre travail, l'idée principale a été d'interpréter la réduction de variance en termes de minimisation d'entropie relative entre une mesure de probabilité optimale donnée, et une famille paramétrique de mesures de probabilité. Nous avons prouvé des résultats théoriques généraux qui définissent un cadre rigoureux d'utilisation de ces méthodes, puis nous avons effectué plusieurs expérimentations en finance et en fiabilité qui justifient de leur efficacité réelle.

APA, Harvard, Vancouver, ISO, and other styles

41

Guo, Chaomei. "Amélioration des propriétés de convergence des algorithmes de simulation des circuits non linéaires microondes." Limoges, 1995. http://www.theses.fr/1995LIMO0024.

Full text

Abstract:

Ce travail propose une etude des methodes d'analyse numerique dans le domaine des circuits non lineaires microondes, basee sur l'amelioration des proprietes de convergence des algorithmes. La principale methode classique de la resolution des equations d'equilibrage harmonique est presentee. Elle est suivie par les descriptions des methodes abs, quasi-newton et de relaxation. Les methodes de type abs sont des methodes iteratives de resolution dont les proprietes de convergence peuvent apporter une amelioration du temps de calcul global. A partir de l'application d'equilibrage harmonique, il est montre que la convergence pres de la solution n'est pas assuree. Les methodes quasi-newton evitent de calculer des derivees partielles pour construire le jacobien en le remplacant par une approximation. Elles laissent envisager une reduction du cout de calcul. Cependant, le gain obtenu par rapport a la methode de newton-raphson reste faible, de l'ordre de 2. Les methodes de relaxation, quant a elles, utilisent les iterations non lineaires lineaires qui peuvent remplacer la resolution exacte de l'equation de recurrence par une resolution approchee. Il est possible de realiser une diminution du cout de calcul a condition que le jacobien soit diagonalement dominant, ce qui n'est pas toujours le cas

APA, Harvard, Vancouver, ISO, and other styles

42

Ho, Zhen Wai Olivier. "Contributions aux algorithmes stochastiques pour le Big Data et à la théorie des valeurs extrèmes multivariés." Thesis, Bourgogne Franche-Comté, 2018. http://www.theses.fr/2018UBFCD025/document.

Full text

Abstract:

La thèse comporte deux parties distinctes. La première partie concerne des modèles pour les extrêmes multivariés.On donne une construction de vecteurs aléatoires multivariés à variations régulières. La construction se base sur une extension multivariée d'un lemme de Breiman établissant la propriété de variation régulière d'un produit $RZ$ de variable aléatoire avec $R$ positive à variation régulière et $Z$ positive suffisamment intégrable. En prenant $mathbf{Z}$ multivarié et suffisamment intégrable, on montre que $Rmathbf{Z}$ est un vecteur aléatoire à variations régulières et on caractérise sa mesure limite. On montre ensuite que pour $mathbf{Z}$ de loi bien choisie, on retrouve des modèles stables classiques comme le modèle t-extremal, Hüsler-Reiss, etc. Puis, on étend notre construction pour considérer la notion de variation régulière multivariée non standard. On montre ensuite que le modèle de Pareto (qu'on appelle Hüsler-Reiss Pareto) associé au modèle max-stable Hüsler-Reiss forme une famille exponentielle complète. On donne quelques propriétés du modèle Hüsler-Reiss Pareto puis on propose un algorithme de simulation exacte. On étudie l'inférence par le maximum de vraisemblance. Finalement, on considère une extension du modèle Hüsler-Reiss Pareto utilisant la notion de variation régulière non standard. On étudie l'inférence par le maximum de vraisemblance du modèle généralisé et on propose une méthode d'estimation des paramètres. On donne une étude numérique sur l'estimateur du maximum de vraisemblance pour le modèle Hüsler-Reiss Pareto. Dans la second partie qui concerne l'apprentissage statistique, on commence par donner une borne sur la valeur singulière minimale d'une matrice perturbée par l'ajout d'une colonne. On propose alors un algorithme de sélection de colonne afin d'extraire les caractéristiques de la matrice. On illustre notre algorithme sur des données réelles de séries temporelles où chaque série est pris comme étant une colonne de la matrice. Deuxièmement, on montre que si une matrice $X$ à une propriété d'incohérence alors $X$ possède aussi une version affaiblie de la propriété NSP (null space property). Puis, on s'intéresse au problème de sélection de matrice incohérente. A partir d'une matrice $Xin mathbb{R}^{n imes p}$ et $mu>0$, on cherche la plus grande sous-matrice de $X$ avec une cohérence inférieure à $mu$. Ce problème est formulé comme un programme linéaire avec contrainte quadratique sur ${0,1}^p$. Comme ce problème est NP-dur, on considère une relaxation sur la sphère et on obtient une borne sur l'erreur lorsqu'on considère le problème relaxé. Enfin, on analyse l'algorithme de gradient stochastique projeté pour l'analyse en composante principale online. On montre qu'en espérance, l'algorithme converge vers un vecteur propre maximum et on propose un algorithme pour sélectionner le pas de l'algorithme. On illustre ensuite cet algorithme par une expérience de simulation
This thesis in divided in two parts. The first part studies models for multivariate extremes. We give a method to construct multivariate regularly varying random vectors. The method is based on a multivariate extension of a Breiman Lemma that states that a product $RZ$ of a random non negative regularly varying variable $R$ and a non negative $Z$ sufficiently integrable is also regularly varying. Replacing $Z$ with a random vector $mathbf{Z}$, we show that the product $Rmathbf{Z}$ is regularly varying and we give a characterisation of its limit measure. Then, we show that taking specific distributions for $mathbf{Z}$, we obtain classical max-stable models. We extend our result to non-standard regular variations. Next, we show that the Pareto model associated with the Hüsler-Reiss max-stable model forms a full exponential family. We show some properties of this model and we give an algorithm for exact simulation. We study the properties of the maximum likelihood estimator. Then, we extend our model to non-standard regular variations. To finish the first part, we propose a numerical study of the Hüsler-Reiss Pareto model.In the second part, we start by giving a lower bound of the smallest singular value of a matrix perturbed by appending a column. Then, we give a greedy algorithm for feature selection and we illustrate this algorithm on a time series dataset. Secondly, we show that an incoherent matrix satisfies a weakened version of the NSP property. Thirdly, we study the problem of column selection of $Xinmathbb{R}^{n imes p}$ given a coherence threshold $mu$. This means we want the largest submatrix satisfying some coherence property. We formulate the problem as a linear program with quadratic constraint on ${0,1}^p$. Then, we consider a relaxation on the sphere and we bound the relaxation error. Finally, we study the projected stochastic gradient descent for online PCA. We show that in expectation, the algorithm converges to a leading eigenvector and we suggest an algorithm for step-size selection. We illustrate this algorithm with a numerical experiment

APA, Harvard, Vancouver, ISO, and other styles

43

Kosuch, Stefanie. "Stochastic Optimization Problems with Knapsack Constraint." Paris 11, 2010. http://www.theses.fr/2010PA112154.

Full text

Abstract:

Etant donné un ensemble d'objets, chacun ayant un poids et une valeur. Le problème de sac-à-dos consiste à choisir un sous-ensemble d'objets qui (i) respecte une certaine restriction du poids (la capacité du sac-à-dos) et (ii) dont la valeur totale est maximisée. Dans cette thèse nous étudions quatre problèmes d'optimisation stochastique avec contrainte de sac-à-dos: le problème de sac-à-dos avec recours simple, le problème de sac-à-dos avec contrainte probabiliste, le problème de sac-à-dos avec recours et un problème bi-niveau stochastique avec contrainte de sac-à-dos probabiliste. Les problèmes ont en commun que les poids dans la contrainte de sac-à-dos sont supposés être aléatoires. Nous proposons de résoudre les problèmes du sac-à-dos avec recours simple ou avec contrainte probabiliste en appliquant un algorithme « branch-and-bound ». Des bornes supérieures sont obtenues en résolvant des relaxations continues. Pour ceci, nous appliquons un algorithme de gradient stochastique. Concernant le cas du sac-à-dos avec recours, nous traitons dans un premier temps le problème avec des poids gaussiens et nous proposons des bornes inférieures et supérieures sur sa valeur optimale. Dans un deuxième temps, nous étudions le cas d’une distribution discrète des poids. Nous montrons que (si P n'est pas égal à NP) le problème déterministe équivalent n’admet pas d’algorithme d’approximation avec une garantie de performance égale à une valeur constante. Le problème bi-niveau stochastique avec contrainte de sac-à-dos probabiliste est d’abord reformulé comme un problème bilinéaire. Ce dernier étant difficile à résoudre à l’optimum, nous proposons de résoudre une relaxation avec un nouvel algorithme itératif
Given a set of objects each having a particular weight and value. The knapsack problem consists of choosing among these items a subset such that (i) the total weight of the chosen items does respect a given weight constraint (the capacity of the knapsack) and (ii) the total value of the chosen items is maximized. In this thesis, we study four stochastic optimization problems with knapsack constraint: the simple recourse knapsack problem, the chance-constrained knapsack problem, the two-stage knapsack problem and a bilievel problem with knapsack chance-constraint. All problems have in common that the item weights in the knapsack constraints are assumed to be random. We propose to solve the simple recourse and the chance-constrained knapsack problems using a branch-&-bound algorithm as framework. Upper bounds are obtained by solving relaxed, i. E. Continuous sub-problems. The latter is done by applying a stochastic gradient algorithm. Concerning the two-stage knapsack problem, we treat, in the first instance, the model where the item weights are assumed to be normally distributed and propose upper and lower bounds on the optimal solution value. Then, we study the problem with discretely distributed weights and show that its deterministic equivalent reformulation does not admit a constant factor approximation algorithm unless P=NP. The studied bilevel problem with knapsack chance-constraint is first of all reformulated as a deterministic equivalent bilinear problem. As the latter is generally hard to solve exactly, we propose to solve a relaxation using a novel iterative algorithm

APA, Harvard, Vancouver, ISO, and other styles

44

Cénac, Peggy. "Récursivité au carrefour de la modélisation de séquences, des arbres aléatoires, des algorithmes stochastiques et des martingales." Habilitation à diriger des recherches, Université de Bourgogne, 2013. http://tel.archives-ouvertes.fr/tel-00954528.

Full text

Abstract:

Ce mémoire est une synthèse de plusieurs études à l'intersection des systèmes dynamiques dans l'analyse statistique de séquences, de l'analyse d'algorithmes dans des arbres aléatoires et des processus stochastiques discrets. Les résultats établis ont des applications dans des domaines variés allant des séquences biologiques aux modèles de régression linéaire, processus de branchement, en passant par la statistique fonctionnelle et les estimations d'indicateurs de risque appliqués à l'assurance. Tous les résultats établis utilisent d'une façon ou d'une autre le caractère récursif de la structure étudiée, en faisant apparaître des invariants comme des martingales. Elles sont au coeur de ce mémoire, utilisées comme outils dans les preuves ou comme objets d'étude.

APA, Harvard, Vancouver, ISO, and other styles

45

Lèbre, Sophie. "Analyse de processus stochastiques pour la génomique : étude du modèle MTD et inférence de réseaux bayésiens dynamiques." Evry-Val d'Essonne, 2007. http://www.biblio.univ-evry.fr/theses/2007/interne/2007EVRY0017.pdf.

Full text

Abstract:

Cette thèse porte sur l'analyse de séquences d'ADN et de données temporelles d'expression de gènes. Nous étudions tout d'abord un modèle parcimonieux de mélange de transition markoviennes (MTD) et introduisons un algorithme EM pour son estimation. Nous présentons ensuite deux approches pour la reconstruction de réseaux génétiques utilisant des réseaux bayésiens dynamiques (DBN). Les dépendances sont décrites par un graphe orienté dont on cherche à estimer la topologie malgré le très faible nombre de mesures par rapport au nombre de gènes observés. Nous supposons d'abord une topologie fixe au cours du temps, approchons ce graphe en considérant des dépendances d'ordre partiel et développons une procédure déterministe d'inférence de DBN. Nous considérons ensuite un modèle de régression à ruptures multiples définissant une suite de phases homogènes. La position des points de rupture et la structure de chaque phase sont estimés simultanément grâce à une procédure MCMC à sauts réversibles
This thesis deals with DNA sequence and time series gene expression analysis. First we study the parsimonious Markov model called Mixture Transition Distribution (MTD) model and introduce an EM algorithm for MTD models estimation. Then we propose two approaches for genetic network recovering using Dynamic Bayesian Networks (DBNs). The dependencies are described by a directed graph whose topology has to be inferred despite the overly low number of repeated measurements compared with the number of observed genes. First we assume that the topology is constant across time, we approximate this graph by considering partial order dependencies and we develop a deterministic procedure for DBNs inference. Then we consider a multiple changepoint regression model defining a succession of homogeneous phases. The changepoints location and the structure within each phase are simultaneously inferred thanks to a reversible jump MCMC procedure

APA, Harvard, Vancouver, ISO, and other styles

46

Xu, Jian. "Modèles stochastiques évolutionnaires pour la gestion de tournées de véhicules avec fenêtres de temps souples et demandes floues." Artois, 2007. http://www.theses.fr/2007ARTO0202.

Full text

Abstract:

Le travail réalisé dans cette thèse traite le problème de la gestion de tournées de véhicules avec fenêtres de temps et demandes floues (VRPTWFD : Vehicle Routing Problem with Time Windows and Fuzzy Demands). Ce problème consiste à trouver des chemins avec un coût minimum pour que les véhicules puissent visiter exactement une fois chaque client en respectant des contraintes. Les clients spécifient leur demande à l’aide d’un nombre flou pour une plus grande souplesse. Le VRPTWFD est étudié dans un contexte aussi bien statique que dynamique. La théorie des possibilités nous a permis d’exprimer la contrainte de capacité floue en fixant des valeurs de seuils de possibilité et de nécessité. En utilisant cette contrainte de capacité floue, un modèle de programmation sous contraintes probabilistes (CCP) et un modèle à deux-étapes de programmation stochastique avec recours (SPR) ont été proposés pour traiter le VRPTWFD. Des algorithmes génétiques qui intègrent ces modèles, ont été proposés pour la recherche de bonnes solutions. Dans le VRPTWFD dynamique, des nouveaux clients arrivent au cours de la journée. Une plateforme de simulation ayant la capacité de simuler la journée de service, nous a permis de résoudre le VRPTWFD dynamique « en ligne ». Afin de vérifier les performances de ces modèles, nous avons construit un benchmark pour le VRPTWFD statique et un benchmark pour le VRPTWFD dynamique en modifiant le jeu de problèmes fournis par Solomon pour le VRPTW, puis nous avons évalué la qualité des solutions fournies par les modèles dans un environnement réel en simulant les situations réelles à l’aide de scénarios « test »
The work of this thesis considers the vehicle routing problem with time windows and fuzzy demands (VRPTWFD). The goal of the problem is to find the routes of the vehicles with a minimal cost so that the vehicles can service each client exactly only once respecting some constraints. The customers specify their demands by a fuzzy number. The VRPTWFD is studied as the static case as well as the dynamic case. We use the possibility theory to handle the constraint of capacity by setting certain thresholds for the degrees of the possibility and necessity. Using this capacity constraint, a chance constrained programming model (CCP) and a two-stages stochastic programming with recourse model (SPR) in stochastic programming were proposed to treat the VRPTWFD. The genetic algorithms integrating these models have been proposed as the optimization approach in order to find the optimal solutions. In the dynamic VRPTWFD, some customers can call in their orders during the daily operation. A simulation platform, which has the capability of simulating the daily operation, has been developed to solve online the dynamic VRPTWFD. In order to assess the performance of the proposed models, we have constructed a benchmark for the static VRPTWFD and a benchmark for the dynamic VRPTWFD adapting from Solomon’s benchmark for the VRPTW, then we have evaluated the quality of the solutions, which were obtained by using these models, by simulating the real world situations with the help of the “test” scenarios

APA, Harvard, Vancouver, ISO, and other styles

47

Gratton, Serge. "Outils théoriques d'analyse du calcul à précision finie." Toulouse, INPT, 1998. http://www.theses.fr/1998INPT015H.

Full text

Abstract:

Nous présentons une théorie générale pour l'étude de la qualité du calcul en précision finie qui s'appuie sur la notion clé de calculabilité en précision finie. Une fois la calculabilité démontrée, se pose alors la question cruciale de la qualité des solutions obtenues par un calcul à précision finie. Pour y répondre, on utilise les notions d'erreur inverses et de conditionnement qui font partie de l'analyse inverse des erreurs introduite par Wilkinson. Nous appliquons cette théorie sur différents exemples issus de l'Algèbre Linéaire et de l'Optimisation. Nous présentons des formules explicites de conditionnement et d'erreur inverses sur divers problèmes d'Algèbre Linéaire. Nous proposons aussi une méthode systématique, fondée sur le produit de Kronecker, qui permet d'obtenir des formules explicites de conditionnements pour de nombreux problèmes. Nous étudions la notion de distance à la singularité dans le cas de polynômes d'une variable réelle ou complexe, ainsi que son lien avec le conditionnement. Nous montrons l'importance de cette notion pour la compréhension du comportement d'algorithmes de recherche de racines de polynômes en précision finie. Conditionnement et erreur inverse sont au cœur de l'étude approfondie que nous consacrons à deux méthodes numériques : les itérations successives pour la résolution de systèmes linéaires, et la méthode de Gauss-Newton pour la résolution de problèmes de moindres carrés non linéaires. Il apparaît que, même prouvé convergent en arithmétique exacte, un algorithme peut diverger lorsqu'il est employé en précision finie, et nous insistons sur la nécessité de disposer de condition de convergence robustes à la précision finie. De nombreux résultats développés dans cette thèse ont été obtenus dans le cadre d'une collaboration entre le CERFACS et le CNES centrée autour d'un problème de restitution d'orbite de satellite.

APA, Harvard, Vancouver, ISO, and other styles

48

Rey, Christian. "Développement d'algorithmes parallèles de résolution en calcul non-linéaire de structures hétérogènes : application au cas d'une butée acier élastomère." Cachan, Ecole normale supérieure, 1994. http://www.theses.fr/1994DENS0025.

Full text

Abstract:

La simulation numérique de structures telles que les supports élastiques (structures multicouches acier élastomère) constitue une étape essentielle d'aide à la conception et à l'optimisation de pièces industrielles. Pour ce faire, nous avons envisagé deux familles de méthodes. La première, la plus classique, consiste à résoudre le problème issu d'une formulation variationnelle en déplacement par des techniques de type newton. La deuxième, peut-être la plus mécanique, résulte d'une formulation lagrangienne augmentée induite par un découplage déplacement/déformation dans la densité d'énergie de déformation (formulation mixte). Le problème est alors résolu par la technique d'Uzawa couplée à une relaxation par bloc. Mais la mise en oeuvre de ces méthodes sur calculateurs séquentiels se révèle souvent impossible en raison de capacités mémoire limitées et de temps de calcul excessifs. Nous étudions différentes mises en oeuvre numériques adaptées à l'architecture parallèle de la nouvelle génération des super-calculateurs scientifiques. Celles-ci reposent sur une utilisation, couplée à l'algorithme du gradient conjugué, de techniques de sous-structuration performantes. Nous avons ainsi également envisage un précautionneusement adapté et une reorthogonalisation totale des directions de descente. En outre, les algorithmes non linéaires envisagés nécessitent la résolution successive de systèmes linéaires, nous proposons une technique dite de correction Krylov permettant d'accélérer sensiblement la résolution d'un système linéaire à partir des informations obtenues a l'issue de la résolution des systèmes précédents. Afin d'illustrer la capacité de ces méthodes à traiter un problème concret, une étude du comportement en compression et en torsion d'une butée acier élastomère est menée. Nous comparons également nos résultats à ceux obtenus par un logiciel industriel

APA, Harvard, Vancouver, ISO, and other styles

49

Pourzandi, Makan. "Etude de l'impact des recouvrements calcul-communication sur des algorithmes parallèles de calcul matriciel." Lyon 1, 1995. http://www.theses.fr/1995LYO19001.

Full text

Abstract:

Dans cette these, nous nous interessons au probleme du recouvrement calcul/communication sur les algorithmes paralleles et ce que cette approche peut apporter a une amelioration des performances des algorithmes paralleles. Les codes paralleles ont souvent ete consideres comme des phases de calcul entrecoupees de phases de communication. Dans cette perspective, toute amelioration du code passait par la diminution separee du cout des communications ou de celui des calculs. Nous entendons par une diminution separee que les programmeurs travaillaient soit uniquement sur la partie communications ou soit uniquement sur la partie calcul. Dans la nouvelle generation de machines paralleles, chaque nud possede un processeur dedie aux communications. Pour pouvoir beneficier au maximum des possibilites des machines, il convient de pouvoir utiliser de maniere simultanee les processeurs de calcul et de communication. Le recouvrement calcul/communication consiste a utiliser le temps de calcul pour effectuer des communications en parallele. Cette approche nous permet de mieux concevoir les algorithmes dans leur ensemble, c'est a dire avec leurs parties de calcul et leurs parties de communication afin d'ameliorer la performance totale. Dans cette these, nous montrons les ameliorations possibles sur plusieurs exemples d'algorithmes paralleles: l'elimination de gauss, la multiplication de matrices et la methode de jacobi pour le calcul des valeurs propres. Afin d'utiliser au maximum les capacites des machines paralleles, nous explorons une nouvelle methode algorithmique pour le calcul des valeurs propres qui malgre ses faibles performances sequentielles est tres efficace en parallele. Nous validons ces methodes d'optimisation algorithmique avec l'optimisation de l'implementation parallele d'une application de simulation de la diffusion de polluants

APA, Harvard, Vancouver, ISO, and other styles

50

Márquez, David. "Vitesse du recuit simulé vectoriel continu ou discrétisé et algorithmes stochastiques en problèmes inverses bayésiens avec applications à la géophysique." Marne-la-Vallée, 1998. http://www.theses.fr/1998MARN0024.

Full text

Abstract:

Cette these concerne deux sujets de differentes natures. Le premier sujet, developpe dans les chapitres 1 et 2, aborde le probleme d'optimisation globale d'une fonction dans r#d, pour lequel on a recours a des algorithmes stochastiques du type recuit simule. Des nouveaux resultats asymptotiques sont obtenus pour des algorithmes a temps continu et un nouvel algorithme discretise est propose pour lequel on donne des vitesses precises de convergence. Le second sujet, aborde dans le chapitre 3, concerne les problemes inverses bayesiens et tout particulierement les modeles geophysiques. Des algorithmes stochastiques de chaines de markov sont utilises pour la simulation / maximisation de certaines lois a posteriori et fonctions de vraisemblance, et des resultats pratiques sont presentes sur divers problemes d'estimation en l'imagerie electromagnetique. L'algorithme du recuit simule a ete largement etudie dans differents cadres a temps discret ou continu et pour un espace d'etats discret ou continu. Le premiere chapitre etudie la diffusion non homogene, dite du recuit simule, dont le coefficient de diffusion, representant la temperature, est une fonction qui decroit logarithmiquement vers zero, et le terme de derive est le gradient du potentiel. La convergence en probabilite de cette diffusion vers les minima globaux du potentiel a ete etablie dans nombreux travaux. On precise la vitesse de cette convergence en loi ou en grandes deviations. Ces resultats theoriques peuvent aider a comprendre la dynamique de telles diffusions non homogenes, en vue d'eventuelles methodes d'acceleration. Lorsque l'espace d'etat est discret, nombreux sont les resultats qui assurent la convergence en probabilite de l'algorithme du recuit simule vers l'ensemble des minima globaux du potentiel. Le cas discret permet aussi des resultats precis sur la vitesse de convergence de l'algorithme, a la difference du cas vectoriel ou, a notre connaissance, seulement des bornes asymptotiques ont ete etablies. Le second chapitre propose alors un algorithme qui reduit au cas discret le probleme d'optimisation, avec un recuit simule par palier sur un reseau qui devient de plus en plus fin. L'aspect le plus interessant de cette methode est qu'elle nous permet d'etablir des resultats tant precis qu'asymptotiques pour differents reglages de la temperature et des pas de discretisation

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Algorithmes de Newton stochastiques'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles