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.

En anatomie computationnelle, on suppose que les formes d'organes sont issues des déformations d'un template commun. Les données peuvent être des images ou des surfaces d'organes, les déformations peuvent être des difféomorphismes. Pour estimer le template, on utilise souvent un algorithme appelé «max-max» qui minimise parmi tous les candidats, la somme des carrées des distances après recalage entre les données et le template candidat. Le recalage est l'étape de l'algorithme qui trouve la meilleure déformation pour passer d'une forme à une autre. Le but de cette thèse est d'étudier cet algorithme max-max d'un point de vue mathématique. En particulier, on prouve que cet algorithme est inconsistant à cause du bruit. Cela signifie que même avec un nombre infini de données et avec un algorithme de minimisation parfait, on estime le template original avec une erreur non nulle. Pour prouver l'inconsistance, on formalise l'estimation du template. On suppose que les déformations sont des éléments aléatoires d'un groupe qui agit sur l'espace des observations. L'algorithme étudié est interprété comme le calcul de la moyenne de Fréchet dans l'espace des observations quotienté par le groupe des déformations. Dans cette thèse, on prouve que l'inconsistance est dû à la contraction de la distance quotient par rapport à la distance dans l'espace des observations. De plus, on obtient un équivalent de biais de consistance en fonction du niveau de bruit. Ainsi, l'inconsistance est inévitable quand le niveau de bruit est suffisamment grand. / In computational anatomy, organ shapes are assumed to be deformation of a common template. The data can be organ images but also organ surfaces, and the deformations are often assumed to be diffeomorphisms. In order to estimate the template, one often uses the max-max algorithm which minimizes, among all the prospective templates, the sum of the squared distance after registration between the data and a prospective template. Registration is here the step of the algorithm which finds the best deformation between two shapes. The goal of this thesis is to study this template estimation method from a mathematically point of view. We prove in particular that this algorithm is inconsistent due to the noise. This means that even with an infinite number of data, and with a perfect minimization algorithm, one estimates the original template with an error. In order to prove inconsistency, we formalize the template estimation: deformations are assumed to be random elements of a group which acts on the space of observations. Besides, the studied algorithm is interpreted as the computation of the Fréchet mean in the space of observations quotiented by the group of deformations. In this thesis, we prove that the inconsistency comes from the contraction of the distance in the quotient space with respect to the distance in the space of observations. Besides, we obtained a Taylor expansion of the consistency bias with respect to the noise level. As a consequence, the inconsistency is unavoidable when the noise level is high.