Cette thèse s'intéresse à la résolution de problèmes d'optimisation non-differentiable de grandes tailles résultant le plus souvent d'une relaxation Lagrangienne d'un problème difficile. Cette technique est couramment utilisée pour appréhender des problèmes linéaires avec nombres entiers ou des problèmes convexes complexes. Le problème dual obtenu est non-différentiable - éventuellement séparable - et peut être résolu par exemple par un algorithme de faisceau. Le Chapitre 2 propose une revue de littérature des méthodes d'optimisation non-différentiable. Dans certaines situations, le problème dual peut être lui-même très difficile à résoudre et nécessiter des stratégies adaptées. Par exemple, lorsque le nombre de contraintes dualisées est très élevé, une dualisation explicite peut s'avérer impossible ou la mise a jour des variables duales peut échouer. Au Chapitre 3, nous étudions les propriétés de convergence lorsqu'une relaxation Lagrangienne dynamique est effectuée : seul un sous-ensemble de contraintes est dualisé a chaque itération, ce qui permet de réduire la dimension du problème dual. Une autre limite de la relaxation Lagrangienne peut apparaître lorsque la fonction duale est séparable en un grand nombre de sous fonctions, ou que celles-ci restent difficiles a évaluer. Une stratégie naturelle consiste alors à tirer partie de la structure séparable en effectuant des itérations duales en n'ayant évalué qu'un sous-ensemble des sous fonctions. Au chapitre 4, nous proposons d'utiliser une méthode de faisceau dans ce contexte incrémental. Enfin, le Chapitre 5 présente des applications numériques sur des problèmes de gestion de production d'électricité.

Etude théorique et algorithmique des problèmes d'optimisation non convexes et non différentiables des types suivants: maximiser f(x) sur C, minimiser f(x)-g(x) sur C, minimiser f(x) lorsque x appartient à C et g(x) positive, où f, g sont convexes définies sur rn et C est une partie compacte convexe non vide de rn. Un étudie les conditions nécessaires d'optimalité du premier ordre la dualité, les méthodes de sous-gradients qui convergent vers des solutions optimales locales et les algorithmes qui permettent d'obtenir les solutions globales. On donne, quelques résultats numériques et applications des algorithmes présentés

Cette thèse présente l’étude d’un problème de contrôle optimal dont le coût est non-différentiable pourcertaines valeurs du contrôle ou de l’état, tout en restant Lipschitz. Ce problème nous a été inspiré par laproblématique générale de la minimisation de l’énergie dépensée par un véhicule ou robot de type voiture lelong d’un trajet dont le profil de route est connu à l’avance. Cette problématique est formulée à l’aide d’unmodèle simple de la dynamique longitudinale du véhicule et une fonction coût qui englobe la notiond’efficacité du processus de conversion énergétique. Nous présentons un résultat de régularité des contrôles,valable pour la classe des systèmes non-linéaires, affines dans les contrôles, classe à laquelle appartient notreproblème. Ce résultat nous permet d’exclure les phénomènes de chattering de l’ensemble des solutions. Nousréalisons trois études de cas pour lesquelles les trajectoires optimales sont composées d’arcs bang,d’inactivations, d’arcs singuliers et, dans certains cas, de retours en arrière. / The present thesis is a study of an optimal control problem having a non-differentiable, but Lipschitz, costfunction. It is inspired by the minimization of the energy consumption of a car-like vehicle or robot along aroad which profile is known. This problem is stated by means of a simple model of the longitudinal dynamicsand a running cost that comprises both an absolute value function and a function that accounts for theefficiency of the energy conversion process. A regularity result that excludes chattering phenomena from theset of solutions is proven. It is valid for the class of control affine systems, which includes the consideredproblem. Three case studies are detailed and analysed. The optimal trajectories are shown to be made of bang,inactivated and backward arcs.

The escape of trajectories is a ubiquitous phenomenon in open dynamical systems and stochastic processes. If escape occurs repetitively for a statistical ensemble of trajectories, the population of remaining trajectories often undergoes an exponential decay characterised by the so-called escape rate. Its inverse defines the lifetime of the decaying state, which represents an intrinsic property of the system. This paradigm is fundamental to nucleation theory and reaction-rate theory in chemistry, physics, and biology.<p><p>In many circumstances, escape is activated by the presence of noise, which may be of internal or external origin. This is the case for thermally activated escape over a potential energy barrier and, more generally, for noise-induced escape in continuous-time or discrete-time dynamics. <p><p>In the weak-noise limit, the escape rate is often observed to decrease exponentially with the inverse of the noise amplitude, a behaviour which is given by the van't Hoff-Arrhenius law of chemical kinetics. In particular, the two important quantities to determine in this case are the exponential dependence (the ``activation energy') and its prefactor.<p><p>The purpose of the present thesis is to develop an analytical method to determine these two quantities. We consider in particular one-dimensional continuous and discrete-time systems perturbed by Gaussian white noise and we focus on the escape from the basin of attraction of an attracting fixed point.<p><p>In both classes of systems, using path-integral methods, a formula is deduced for the noise-induced escape rate from the attracting fixed point across an unstable fixed point, which forms the boundary of the basin of attraction. The calculation starts from the trace formula for the eigenvalues of the operator ruling the time evolution of the probability density in noisy maps. The escape rate is determined by the loop formed by two heteroclinic orbits connecting back and forth the two fixed points in a two-dimensional auxiliary deterministic dynamical system. The escape rate is obtained, including the expression of the prefactor to van't Hoff-Arrhenius exponential factor./L'échappement des trajectoires est un phénomène omniprésent dans les systèmes dynamiques ouverts et les processus stochastiques. Si l'échappement se produit de façon répétitive pour un ensemble statistique de trajectoires, la population des trajectoires restantes subit souvent une décroissance exponentielle caractérisée par le taux d'échappement. L'inverse du taux d'échappement définit alors la durée de vie de l'état transitoire associé, ce qui représente une propriété intrinsèque du système. Ce paradigme est fondamental pour la théorie de la nucléation et, de manière générale, pour la théorie des taux de transitions en chimie, en physique et en biologie.<p><p>Dans de nombreux cas, l'échappement est induit par la présence de bruit, qui peut être d'origine interne ou externe. Ceci concerne en particulier l'échappement activé thermiquement à travers une barrière d'énergie potentielle, et plus généralement, l'échappement dû au bruit dans les systèmes dynamiques à temps continu ou à temps discret.<p><p>Dans la limite de faible bruit, on observe souvent une décroissance exponentielle du taux d'échappement en fonction de l'inverse de l'amplitude du bruit, un comportement qui est régi par la loi de van't Hoff-Arrhenius de la cinétique chimique. En particulier, les deux quantités importantes de cette loi sont le coefficient de la dépendance exponentielle (c'est-à-dire ``l'énergie d'activation') et son préfacteur.<p><p>L'objectif de cette thèse est de développer une théorie analytique pour déterminer ces deux quantités. La théorie que nous présentons concerne les systèmes unidimensionnels à temps continu ou discret perturbés par un bruit blanc gaussien et nous considérons le problème de l'échappement du bassin d'attraction d'un point fixe attractif. Pour s'échapper, les trajectoires du système bruité initialement contenues dans ce bassin d'attraction doivent alors traverser un point fixe instable qui forme la limite du bassin.<p><p>Dans le présent travail, et pour les deux types de systèmes, une formule est dérivée pour le taux d'échappement du point fixe attractif en utilisant des méthodes d'intégrales de chemin. Le calcul utilise la formule de trace pour les valeurs propres de l'opérateur gouvernant l'évolution temporelle de la densité de probabilité dans le système bruité. Le taux d'échappement est déterminé en considérant la boucle formée par deux orbites hétéroclines liant dans les deux sens les deux points fixes dans un système dynamique auxiliaire symplectique et bidimensionnel. On obtient alors le taux d'échappement, comprenant l'expression du préfacteur de l'exponentielle de la loi de van't Hoff-Arrhenius. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Un objectif de longue date dans le domaine de la vision par ordinateur est de déduire le contenu 3D d’une scène à partir d’une seule photo, une tâche connue sous le nom d’inverse graphics. L’apprentissage automatique a, dans les dernières années, permis à de nombreuses approches de faire de grands progrès vers la résolution de ce problème. Cependant, la plupart de ces approches requièrent des données de supervision 3D qui sont coûteuses et parfois impossible à obtenir, ce qui limite les capacités d’apprentissage de telles œuvres. Dans ce travail, nous explorons l’architecture des méthodes d’inverse graphics non-supervisées et proposons deux méthodes basées sur des représentations 3D et algorithmes de rendus différentiables distincts: les surfels ainsi qu’une nouvelle représentation basée sur Voronoï. Dans la première méthode basée sur les surfels, nous montrons que, bien qu’efficace pour maintenir la cohérence visuelle, la production de surfels à l’aide d’une carte de profondeur apprise entraîne des ambiguïtés car la relation entre la carte de profondeur et le rendu n’est pas bijective. Dans notre deuxième méthode, nous introduisons une nouvelle représentation 3D basée sur les diagrammes de Voronoï qui modélise des objets/scènes à la fois explicitement et implicitement, combinant ainsi les avantages des deux approches. Nous montrons comment cette représentation peut être utilisée à la fois dans un contexte supervisé et non-supervisé et discutons de ses avantages par rapport aux représentations 3D traditionnelles / A long standing goal of computer vision is to infer the underlying 3D content in a scene from a single photograph, a task known as inverse graphics. Machine learning has, in recent years, enabled many approaches to make great progress towards solving this problem. However, most approaches rely on 3D supervision data which is expensive and sometimes impossible to obtain and therefore limits the learning capabilities of such work. In this work, we explore the deep unsupervised inverse graphics training pipeline and propose two methods based on distinct 3D representations and associated differentiable rendering algorithms: namely surfels and a novel Voronoi-based representation. In the first method based on surfels, we show that, while effective at maintaining view-consistency, producing view-dependent surfels using a learned depth map results in ambiguities as the mapping between depth map and rendering is non-bijective. In our second method, we introduce a novel 3D representation based on Voronoi diagrams which models objects/scenes both explicitly and implicitly simultaneously, thereby combining the benefits of both. We show how this representation can be used in both a supervised and unsupervised context and discuss its advantages compared to traditional 3D representations.

L'intelligence artificielle (IA) moderne a ouvert de nouvelles perspectives prometteuses pour la création de robots intelligents. En particulier, les architectures d'apprentissage basées sur le gradient (réseaux neuronaux profonds) ont considérablement amélioré la compréhension des scènes 3D en termes de perception, de raisonnement et d'action. Cependant, ces progrès ont affaibli l'attrait de nombreuses techniques ``classiques'' développées au cours des dernières décennies. Nous postulons qu'un mélange de méthodes ``classiques'' et ``apprises'' est la voie la plus prometteuse pour développer des modèles du monde flexibles, interprétables et exploitables : une nécessité pour les agents intelligents incorporés. La question centrale de cette thèse est : ``Quelle est la manière idéale de combiner les techniques classiques avec des architectures d'apprentissage basées sur le gradient pour une compréhension riche du monde 3D ?''. Cette vision ouvre la voie à une multitude d'applications qui ont un impact fondamental sur la façon dont les agents physiques perçoivent et interagissent avec leur environnement. Cette thèse, appelée ``programmes différentiables pour modèler l'environnement'', unifie les efforts de plusieurs domaines étroitement liés mais actuellement disjoints, notamment la robotique, la vision par ordinateur, l'infographie et l'IA. Ma première contribution---gradSLAM--- est un système de localisation et de cartographie simultanées (SLAM) dense et entièrement différentiable. En permettant le calcul du gradient à travers des composants autrement non différentiables tels que l'optimisation non linéaire par moindres carrés, le raycasting, l'odométrie visuelle et la cartographie dense, gradSLAM ouvre de nouvelles voies pour intégrer la reconstruction 3D classique et l'apprentissage profond. Ma deuxième contribution - taskography - propose une sparsification conditionnée par la tâche de grandes scènes 3D encodées sous forme de graphes de scènes 3D. Cela permet aux planificateurs classiques d'égaler (et de surpasser) les planificateurs de pointe basés sur l'apprentissage en concentrant le calcul sur les attributs de la scène pertinents pour la tâche. Ma troisième et dernière contribution---gradSim--- est un simulateur entièrement différentiable qui combine des moteurs physiques et graphiques différentiables pour permettre l'estimation des paramètres physiques et le contrôle visuomoteur, uniquement à partir de vidéos ou d'une image fixe. / Modern artificial intelligence (AI) has created exciting new opportunities for building intelligent robots. In particular, gradient-based learning architectures (deep neural networks) have tremendously improved 3D scene understanding in terms of perception, reasoning, and action. However, these advancements have undermined many ``classical'' techniques developed over the last few decades. We postulate that a blend of ``classical'' and ``learned'' methods is the most promising path to developing flexible, interpretable, and actionable models of the world: a necessity for intelligent embodied agents. ``What is the ideal way to combine classical techniques with gradient-based learning architectures for a rich understanding of the 3D world?'' is the central question in this dissertation. This understanding enables a multitude of applications that fundamentally impact how embodied agents perceive and interact with their environment. This dissertation, dubbed ``differentiable world programs'', unifies efforts from multiple closely-related but currently-disjoint fields including robotics, computer vision, computer graphics, and AI. Our first contribution---gradSLAM---is a fully differentiable dense simultaneous localization and mapping (SLAM) system. By enabling gradient computation through otherwise non-differentiable components such as nonlinear least squares optimization, ray casting, visual odometry, and dense mapping, gradSLAM opens up new avenues for integrating classical 3D reconstruction and deep learning. Our second contribution---taskography---proposes a task-conditioned sparsification of large 3D scenes encoded as 3D scene graphs. This enables classical planners to match (and surpass) state-of-the-art learning-based planners by focusing computation on task-relevant scene attributes. Our third and final contribution---gradSim---is a fully differentiable simulator that composes differentiable physics and graphics engines to enable physical parameter estimation and visuomotor control, solely from videos or a still image.