Dans cette thèse, nous utilisons différentes inégalités fonctionnelles<br />(Poincaré, Sobolev logarithmique, etc.) pour étudier deux questions.<br />Nous appliquons d'abord des inégalités affaiblies à l'étude d'une<br />diffusion inhomogène, analogue continu de l'algorithme de recuit<br />simulé, dans la lignée d'un travail de L. Miclo. Nous montrons un<br />résultat de convergence de la diffusion, sous des hypothèses plus<br />faibles que celles posées précédemment : le potentiel dans lequel la<br />diffusion évolue peut croître très lentement à l'infini.<br />Dans le cadre d'un modèle de mécanique statistique à spins non-bornés,<br />en nous basant sur des résultats de T. Bodineau et B. Helffer, N. Yoshida<br />et G. Royer, nous éclaircissons ensuite les liens entre différentes<br />inégalités fonctionnelles, des propriétés de mélange et l'unicité de<br />la mesure de Gibbs en volume infini. Nous montrons en particulier<br />l'unicité si les mesures en volume fini et pour une seule condition<br />aux bords vérifient uniformément une inégalité de Beckner.

Cette thèse s'articule autour des fonctions booléennes liées à la cryptographie et la cryptanalyse de certains schémas d'identification. Les fonctions booléennes possèdent des propriétés algébriques fréquemment utilisées en cryptographie pour constituer des S-Boxes (tables de substitution).Nous nous intéressons, en particulier, à la construction de deux types de fonctions : les fonctions courbes et les fonctions équilibrées de haut degré de non-linéarité.Concernant la cryptanalyse, nous nous focalisons sur les techniques d'identification basées sur les problèmes de perceptron et de perceptron permuté. Nous réalisons une nouvelle attaque sur le schéma afin de décider de sa faisabilité.Nous développons ici des nouvelles méthodes combinant l'approche déterministe DCA (Difference of Convex functions Algorithm) et heuristique (recuit simulé, entropie croisée, algorithmes génétiques...). Cette approche hybride, utilisée dans toute cette thèse, est motivée par les résultats intéressants de la programmation DC.

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.

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.

La reconstruction phylogénétique est considérée comme un élément central de divers domaines comme l’écologie, la biologie et la physiologie moléculaire pour lesquels les relations généalogiques entre séquences d’espèces ou de gènes, représentées sous forme d’arbres, peuvent apporter des éclairages significatifs à la compréhension de phénomènes biologiques. Le problème de Maximum de Parcimonie est une approche importante pour résoudre la reconstruction phylogénétique en se basant sur un critère d’optimalité pour lequel l’arbre comprenant le moins de mutations est préféré. Dans cette thèse nous proposons différentes méthodes pour s’attaquer à la nature combinatoire de ce problème NP-complet. Premièrement, nous présentons un algorithme de Recuit Simulé compétitif qui nous a permis de trouver des solutions de meilleure qualité pour un ensemble de problèmes. Deuxièmement, nous proposons une nouvelle technique de Path-Relinking qui semble intéressante pour comparer des arbres mais pas pour trouver des solutions de meilleure qualité. Troisièmement, nous donnons le code d’une implantation sur GPU de la fonction objectif dont l’intérêt est de réduire le temps d’exécution de la recherche pour des instances dont la longueur des séquences est importante. Finalement, nous introduisons un prédicteur capable d’estimer le score optimum pour un vaste ensemble d’instances avec une très grande précision. / Phylogenetic reconstruction is considered a central underpinning of diverse fields like ecology, molecular biology and physiology where genealogical relationships of species or gene sequences represented as trees can provide the most meaningful insights into biology. Maximum Parsimony (MP) is an important approach to solve the phylogenetic reconstruction based on an optimality criterion under which the tree that minimizes the total number of genetic transformations is preferred. In this thesis we propose different methods to cope with the combinatorial nature of this NP-complete problem. First we present a competitive Simulated Annealing algorithm which helped us find trees of better parsimony score than the ones that were known for a set of instances. Second, we propose a Path-Relinking technique that appears to be suitable for tree comparison but not for finding trees of better quality. Third, we give a GPU implementation of the objective function of the problem that can reduce the runtime for instances that have an important number of residues per taxon. Finally, we introduce a predictor that is able to estimate the best parsimony score of a huge set of instances with a high accuracy.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ballista est un nouveau système de planification de traitement qui a été développé en alternative à la radiothérapie par modulation d'intensité. L'optimisation à la base de ce dispositif contrôle la configuration des plans de traitement ainsi que le poids des différents champs générés en vue de moduler la radiation. Malgré sa grande flexibilité, Ballista se limite toutefois à la création de plans monoénergétiques. Ce mémoire s'est donc penché sur le rôle de l'énergie dans les plateformes de planification inverse. Le fonctionnement de Ballista s'appuie sur l'emploi de deux engins d'optimisation distincts : un algorithme de recuit simulé qui gère la configuration du traitement et un algorithme de quasi-Newton avec contraintes qui fixe le poids des différents champs. Afin de tirer profit de la nature bidimensionnelle du système, l'introduction de l'énergie en tant que variable versatile se fait par le biais de l'une ou l'autre de ces techniques de calcul. / Cette stratégie permet de créer des plans multiénergétiques qui possèdent une ou plusieurs énergies par incidence. Une étude rétrospective détaillée de l'efficacité du système a été réalisée sur la base de cinq patients atteints d'un cancer pulmonaire avancé. L'optimisation de l'énergie a en fait permis d'améliorer la conformité des traitements, mais surtout de limiter la dose délivrée aux poumons sains, l'organe à risque le plus problématique pour ce type d'irradiation. L'introduction de ce paramètre dans les procédés d'optimisation semble donc améliorer sensiblement la qualité des plans produits sans alourdir inutilement le poids clinique de la planification.

Résumé indisponible. / A healthcare network or health system consists of all organizations, actions and people who participate to promote, restore or maintain people’s health. The health care systems in many developed countries are facing increasing costs. The major reason is the changing age distribution of the population with more elderly people in need of support. Increasing healthcare costs has created new alternatives to traditional hospitalization in which one is Home Health Care (HHC). Home health care or domiciliary care is the provision of health care and assistance to people in their own homes, according to a formal assessment of their needs. HHC has attained a specific place in healthcare network. HHC programs have now been successfully implemented in many countries. The purpose of HHC is to provide the care and support needed to assist patients to live independently in their own homes. HHC is primarily performed by means of personal visitations of healthcare workers to patients in their homes, where they provide care assistance according to patients’ needs. In this thesis we have considered different aspects of planning problems for home health care services. The efficient use of resources is necessary in continuous healthcare services. To meet the increased demand of HHC, operation research specialist can play an important role by solving the various combinatorial optimization problems arising in HHC. These problems can be tactical, strategic or operational with respect to planning horizon. Strategic problems are those which help in attaining long term goals or objectives, e.g. higher level of quality for HHC patients and efficient use of resources. These strategic objectives can be achieved through tactical i.e. medium term panning and operational planning i.e. short term planning. The main purpose of our thesis is to identify these potential optimization problems and solve them via recent metaheuristics. HHC is an alternative to traditional hospitalization and has got a significant share in the organization of healthcare in developed countries. The change in aging demographics, recent development in technology and the increase in the demand of healthcare services are major reasons for this rapid growth. Some studies show HHC as a tool to reduce costs of care, which is a major preoccupation in developed countries. Some others reveal that it leads to the improvement of patients’ satisfaction without increasing the resources. Home health care, i.e. visiting and nursing patients in their homes, is a flourishing realm in the medical industry. The number of companies has grown largely both in public and private sectors. The staffing needs for HHC companies have been expanded as well. Also they face the problem of assigning geographically dispersed patients to home healthcare workers and preparing daily schedules for these workers. The challenge of this problem is to combine aspects of vehicle routing and staff rostering. Both of them are well known NP- hard combinatorial optimization problems, it means the amount of computational time required to find solution increases exponentially with problem size. Home healthcare workers scheduling problem is difficult to solve optimally due to presence of large number of constraints. These are two types of constraints: hard constraints and soft constraints. The hard constraints are the restrictions to be fulfilled for the schedules to be applicable and soft constraints are preferences to improve the quality of these schedules. (...)

No description available.

Cette thèse se concentre sur deux problèmes tactiques de gestion des chaînes logistiques, la planification tactique et la gestion de stock à demande différenciée. Ainsi, le premier objectif de ce travail est de proposer un modèle de planification tactique générique pour les chaînes logistiques dites à "nomenclature convergente". Une méthode d'optimisation à base de recuit simulé dédié à ce modèle est également proposée. De récents travaux ont montré la pertinence de générer les plans tactiques non plus à partir de ces coûts mais à partir d'indicateurs financiers tels que la la valeur dégagée, etc. Le second objectif de ce mémoire est donc d'étudier les liens entre flux physiques et flux financiers afin de définir des modèles de planification tactique optimisant une fonction financière. La problématique de la répartition de la valeur au sein de la chaîne logistique est également étudiée et nous proposons un modèle mathématique répondant à cette dernière thématique. Une approche intégrée pour la planification tactique d'une chaîne logistique articulée autour d'un chaînage de modèles mathématiques (planification / partage de la valeur) est alors proposée .La deuxième partie de ce mémoire présente l'étude d'un problème de gestion de stock dit à demande différenciée. Une comparaison de plusieurs solutions de gestion est proposée à partir d'un modèle de simulation à événement discret.