De nos jours, les systèmes automatisés sont omniprésent : processus industriels, avionique, énergie atomique... La présence de tels systèmes dans des applications critiques, couplée à leur complexité rend indispensable leur vérification de façon automatique afin de garantir la sûreté de leur fonctionnement. En plus, les contraintes économiques imposent un temps de développement court, ce qui rend accru le besoin de méthodes de vérification efficaces et à coût réduit. Les algorithmes de Model-Checking sont conçus pour la vérification totale des systèmes en parcourant leurs graphes d'états. Cependant, les graphes d'états des systèmes logiciels réels ont de très grandes tailles (explosion combinatoire de la taille de l'espace d'états). Ce phénomène constitue l'obstacle principal de la vérification automatique par model checking. Alternativement, on a recours à l'exploration partiel via des algorithmes randomises. Au lieu d'abandonner l'exploration par manque de ressources et ne retourner aucune réponse quant à la validité du système, le résultat de la vérification est donné approximativement avec une probabilité d'erreur que l'on peut contrôler. La majorité des méthodes randomisées de vérification utilisent la marche aléatoire comme schéma d'exploration. Les méthodes que nous proposons opèrent sur le schéma de l'exploration même ainsi que sur le remplacement en mémoire pour apporter des performances importantes. Ces algorithmes présentent un jeu assez complet de stratégies d'exploration: en profondeur, en largeur, ou alternativement selon un paramètre de mixage prédéfini. Le choix de ce paramètre est guidé par un facteur de densité DF caractéristique du graphe considéré.

À l'ère de la numérisation, les données devient pas cher et facile à obtenir. Cela se traduit par de nombreux nouveaux problèmes d'optimisation avec de très grandes tailles. En particulier, pour le même genre de problèmes, le nombre de variables et de contraintes sont énormes. En outre, dans de nombreux paramètres d'application tels que ceux dans l'apprentissage de la machine, une solution précise est moins préférée que celles approximatives mais robustes. Il est un véritable défi pour les algorithmes traditionnels, qui sont utilisés pour bien travailler avec des problèmes de taille moyenne, pour faire face à ces nouvelles circonstances.Au lieu de développer des algorithmes qui évoluent bien à résoudre ces problèmes directement, une idée naturelle est de les transformer en problèmes de petite taille qui se rapporte fortement aux originaux. Étant donné que les nouvelles sont de tailles gérables, ils peuvent encore être résolus efficacement par des méthodes classiques. Les solutions obtenues par ces nouveaux problèmes, cependant, nous donner un aperçu des problèmes originaux. Dans cette thèse, nous allons exploiter l'idée ci-dessus pour résoudre certains problèmes de grande dimension optimisation. En particulier, nous appliquons une technique spéciale appelée projection aléatoire pour intégrer les données du problème dans les espaces de faible dimension, et de reformuler environ le problème de telle manière qu'il devient très facile à résoudre, mais capte toujours l'information la plus importante.Dans le chapitre 3, nous étudions les problèmes d'optimisation dans leurs formes de faisabilité. En particulier, nous étudions le problème que l'on appelle l'adhésion linéaire restreint. Cette classe contient de nombreux problèmes importants tels que la faisabilité linéaire et entier. Nous proposonsd'appliquer une projection aléatoire aux contraintes linéaires etnous voulons trouver des conditions sur T, de sorte que les deux problèmes de faisabilité sont équivalentes avec une forte probabilité.Dans le chapitre 4, nous continuons à étudier le problème ci-dessus dans le cas où l'ensemble restreint est un ensemble convexe. Nous établissons les relations entre les problèmes originaux et projetés sur la base du concept de la largeur gaussienne, qui est populaire dans la détection comprimé. En particulier, nous montrons que les deux problèmes sont équivalents avec une forte probabilité aussi longtemps que pour une projection aléatoire échantillonné à partir ensemble sous-gaussienne avec grande dimension suffisante (dépend de la largeur gaussienne).Dans le chapitre 5, nous étudions le problème de l'adhésion euclidienne:.. `` Étant donné un vecteur b et un euclidienne ensemble fermé X, décider si b est en Xor pas "Ceci est une généralisation du problème de l'appartenance linéaire restreinte précédemment considéré. Nous employons une gaussienne projection aléatoire T pour l'intégrer à la fois b et X dans un espace de dimension inférieure et étudier la version projetée correspondant. Lorsque X est fini ou dénombrable, en utilisant un argument simple, nous montrons que les deux problèmes sont équivalents presque sûrement quelle que soit la dimension projetée. Dans le cas où X peut être indénombrable, nous prouvons que les problèmes initiaux et prévus sont également équivalentes si la dimension d projetée est proportionnelle à une dimension intrinsèque de l'ensemble X. En particulier, nous employons la définition de doubler la dimension estimer la relation entre les deux problèmes.Dans le chapitre 6, nous proposons d'appliquer des projections aléatoires pour la zone de confiance sous-problème. Nous réduisons le nombre de variables en utilisant une projection aléatoire et prouver que des solutions optimales pour le nouveau problème sont en fait des solutions approchées de l'original. Ce résultat peut être utilisé dans le cadre de confiance-région pour étudier l'optimisation de boîte noire et l'optimisation des produits dérivés libre. / In the digitization age, data becomes cheap and easy to obtain. That results in many new optimization problems with extremely large sizes. In particular, for the same kind of problems, the numbers of variables and constraints are huge. Moreover, in many application settings such as those in Machine learning, an accurate solution is less preferred as approximate but robust ones. It is a real challenge for traditional algorithms, which are used to work well with average-size problems, to deal with these new circumstances.Instead of developing algorithms that scale up well to solve these problems directly, one natural idea is to transform them into small-size problems that strongly relates to the originals. Since the new ones are of manageable sizes, they can still be solved efficiently by classical methods. The solutions obtained by these new problems, however, will provide us insight into the original problems. In this thesis, we will exploit the above idea to solve some high-dimensional optimization problems. In particular, we apply a special technique called random projection to embed the problem data into low dimensional spaces, and approximately reformulate the problem in such a way that it becomes very easy to solve but still captures the most important information. Therefore, by solving the projected problem, we either obtain an approximate solution or an approximate objective value for the original problem.We will apply random projection to study a number of important optimization problems, including linear and integer programming (Chapter 3), convex optimization with linear constraints (Chapter 4), membership and approximate nearest neighbor (Chapter 5) and trust-region subproblems (Chapter 6).In Chapter 3, we study optimization problems in their feasibility forms. In particular, we study the so-called restricted linear membership problem. This class contains many important problems such as linear and integer feasibility. We proposeto apply a random projection to the linear constraints, andwe want to find conditions on T, so that the two feasibility problems are equivalent with high probability.In Chapter 4, we continue to study the above problem in the case the restricted set is a convex set. Under that assumption, we can define a tangent cone at some point with minimal squared error. We establish the relations between the original and projected problems based on the concept of Gaussian width, which is popular in compressed sensing. In particular, we prove thatthe two problems are equivalent with high probability as long as for some random projection sampled from sub-gaussian ensemble with large enough dimension (depends on the gaussian width).In Chapter 5, we study the Euclidean membership problem: ``Given a vector b and a Euclidean closed set X, decide whether b is in Xor not". This is a generalization of the restricted linear membership problem considered previously. We employ a Gaussian random projection T to embed both b and X into a lower dimension space and study the corresponding projected version: ``Decide whether Tb is in T(X) or not". When X is finite or countable, using a straightforward argument, we prove that the two problems are equivalent almost surely regardless the projected dimension. In the case when X may be uncountable, we prove that the original and projected problems are also equivalent if the projected dimension d is proportional to some intrinsic dimension of the set X. In particular, we employ the definition of doubling dimension estimate the relation between the two problems.In Chapter 6, we propose to apply random projections for the trust-region subproblem. We reduce the number of variables by using a random projection and prove that optimal solutions for the new problem are actually approximate solutions of the original. This result can be used in the trust-region framework to study black-box optimization and derivative-free optimization.

La géométrie algorithmique a pour but de concevoir et d'analyser des algorithmes pour résoudre des problèmes géométriques. C'est un domaine récent de l'informatique théorique, qui s'est très rapidement développé depuis son apparition dans la thèse de M. I. Shamos en 1978. La randomisation permet d'éviter le recours à des structures compliquées, et s'avère très efficace, tant du point de vue de la complexité théorique, que des résultats pratiques. Nous nous sommes intéressés plus particulièrement à la conception d'algorithmes dynamiques : en pratique, il est fréquent que l'acquisition des données d'un problème soit progressive. Il n'est évidemment pas question de recalculer le résultat à chaque nouvelle donnée, d'où la nécéssité d'utiliser des schémas (semi-)dynamiques. Nous introduisons une structure très générale, le graphe d'influence, qui permet de construire de nombreuses structures géométriques : diagrammes de Voronoï, arrangements de segments... Nous étudions les algorithmes, à la fois du point de vue de la complexité théorique, de leur mise en oeuvre pratique et de l'efficacité des programmes.

L'objet de cette thèse est le développement et l'étude des algorithmes de planification de mouvement pour les systèmes hautement dimensionnés que sont les robots humanoïdes et les acteurs virtuels. Plusieurs adaptations des méthodes génériques de planification de mouvement randomisées sont proposées et discutées. Une première contribution concerne l'utilisation de techniques de réduction de dimension linéaire pour accélérer les algorithmes d'échantillonnage. Cette méthode permet d'identifier en ligne quand un processus de planification passe par un passage étroit de l'espace des configurations et adapte l'exploration en fonction. Cet algorithme convient particulièrement bien aux problèmes difficiles de la planification de mouvement pour l'animation graphique. La deuxième contribution est le développement d'algorithmes randomisés de planification sous contraintes. Il s'agit d'une intégration d'outils de cinématique inverse hiérarchisée aux algorithmes de planification de mouvement randomisés. On illustre cette méthodes sur différents problèmes de manipulation pour robots humanoïdes. Cette contribution est généralisée à la planification de mouvements corps-complet nécessitant de la marche. La dernière contribution présentée dans cette thèse est l'utilisation des méthodes précédentes pour résoudre des tâches de manipulation complexes par un robot humanoïde. Nous présentons en particulier un formalisme destiné à représenter les informations propres à l'objet manipulé utilisables par un planificateur de mouvement. Ce formalisme est présenté sous le nom d'"objets documentés".

Dans cette Habilitation à Diriger des Recherches (HDR), nous présentons notre recherche effectuée au cours de ces dernières années dans le domaine du calcul haute-performance. Notre travail a porté essentiellement sur les algorithmes parallèles pour les solveurs d'algèbre linéaire numérique et leur implémentation parallèle dans les bibliothèques logicielles du domaine public. Nous illustrons dans ce manuscrit comment ces calculs peuvent être accélérées en utilisant des algorithmes innovants et être rendus fiables en utilisant des quantités spécifiques de l'analyse d'erreur. Nous expliquons tout d'abord comment les solveurs d'algèbre linéaire numérique peuvent être conçus de façon à exploiter les capacités des calculateurs hétérogènes actuels comprenant des processeurs multicœurs et des GPUs. Nous considérons des algorithmes de factorisation dense pour lesquels nous décrivons la répartition des tâches entre les différentes unités de calcul et son influence en terme de coût des communications. Ces cal- culs peuvent être également rendus plus performants grâce à des algorithmes en précision mixte qui utilisent une précision moindre pour les tâches les plus coûteuses tout en calculant la solution en précision supérieure. Puis nous décrivons notre travail de recherche dans le développement de solveurs d'algèbre linéaire rapides qui utilisent des algorithmes randomisés. La randomisation représente une approche innovante pour accélérer les calculs d'algèbre linéaire et la classe d'algorithmes que nous proposons a l'avantage de réduire la volume de communications dans les factorisations en supprimant complètement la phase de pivotage dans les systèmes linéaires. Les logiciels correspondants on été développés pour architectures multicœurs éventuellement accélérées par des GPUs. Enfin nous proposons des outils qui nous permettent de garantir la qualité de la solution calculée pour les problèmes de moindres carrés sur-déterminés, incluant les moindres carrés totaux. Notre méthode repose sur la dérivation de formules exactes ou d'estimateurs pour le conditionnement de ces problèmes. Nous décrivons les algorithmes et les logiciels qui permettent de calculer ces quantités avec les bibliothèques logicielles parallèles standards. Des pistes de recherche pour les années à venir sont données dans un chapître de conclusion.