Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type glouton, et montrons qu’ils sont quasi-optimaux. Nous étudions aussi ces problèmes sur des familles particulières de graphes, démontrons des bornes inférieures, et étudions la reconstruction approximative. Le deuxième sujet est l’étude de deux problèmes d’optimisation sur les graphes planaires. Dans le problème de classification par corrélations, l’entrée est un graphe pondéré, où chaque arête a une étiquette h+i ou h-i, indiquant si ses extrémités sont ou non dans la même catégorie. Le but est de trouver une partition des sommets en catégories qui respecte au mieux les étiquettes. Dans le problème d’augmentation 2-arête-connexe, l’entrée est un graphe pondéré et un sous-ensemble R des arêtes. Le but est de trouver un sous-ensemble S des arêtes de poids minimum, tel que pour chaque arête de R, ses extrémités sont dans une composante 2-arête-connexe de l’union de R et S. Pour les graphes planaires, nous réduisons le premier problème au deuxième et montrons que les deux problèmes, bien que NP-durs, ont un schéma d’approximation en temps polynomial. Nous utilisons la technique récente de décomposition en briques. / This thesis focuses on two topics of graph algorithms. The first topic is network inference. How efficiently can we find an unknown graph using shortest path queries between its vertices? We assume that the graph has bounded degree. In the reconstruction problem, the goal is to find the graph; and in the verification problem, the goal is to check whether a given graph is correct. We provide randomized algorithms based on a Voronoi cell decomposition. Next, we analyze greedy algorithms, and show that they are near-optimal. We also study the problems on special graph classes, prove lower bounds, and study the approximate reconstruction. The second topic is optimization in planar graphs. We study two problems. In the correlation clustering problem, the input is a weighted graph, where every edge has a label of h+i or h−i, indicating whether its endpoints are in the same category or in different categories. The goal is to find a partition of the vertices into categories that tries to respect the labels. In the two-edge-connected augmentation problem, the input is a weighted graph and a subset R of edges. The goal is to produce a minimum-weight subset S of edges, such that for every edge in R, its endpoints are two-edge-connected in the union of R and S. For planar graphs, we reduce correlation clustering to two-edge-connected augmentation, and show that both problems, although they are NP-hard, have a polynomial-time approximation scheme. We build on the brick decomposition technique developed recently.

De nos jours, il est de plus en plus fréquent de travailler sur des bases de données de très grandes tailles dans plein de domaines différents. Cela ouvre la voie à de nouvelles possibilités d'exploitation ou d'exploration de l'information, et de nombreuses technologies numériques ont été créées récemment dans cette optique. D'un point de vue théorique, ce problème nous contraint à revoir notre manière d'analyser et de comprendre les données enregistrées. En effet, dans cet univers communément appelé « Big Data », un bon nombre de méthodes traditionnelles d'inférence statistique multivariée deviennent inadaptées. Le but de cette thèse est donc de mieux comprendre ce phénomène, appelé fléau (ou malédiction) de la dimension, et ensuite de proposer différents outils statistiques exploitant explicitement la dimension du problème et permettant d'extraire des informations fiables des données. Pour cela, nous nous intéresserons beaucoup aux vecteurs propres de matrices symétriques. Nous verrons qu’il est possible d’extraire de l'information présentant un certain degré d’universalité. En particulier, cela nous permettra de construire des estimateurs optimaux, observables, et cohérents avec le régime de grande dimension. / Nowadays, it is easy to get a lot ofquantitative or qualitative data in a lot ofdifferent fields. This access to new databrought new challenges about data processingand there are now many different numericaltools to exploit very large database. In atheoretical standpoint, this framework appealsfor new or refined results to deal with thisamount of data. Indeed, it appears that mostresults of classical multivariate statisticsbecome inaccurate in this era of “Big Data”.The aim of this thesis is twofold: the first one isto understand theoretically this so-called curseof dimensionality that describes phenomenawhich arise in high-dimensional space.Then, we shall see how we can use these toolsto extract signals that are consistent with thedimension of the problem. We shall study thestatistics of the eigenvalues and especially theeigenvectors of large symmetrical matrices. Wewill highlight that we can extract someuniversal properties of these eigenvectors andthat will help us to construct estimators that areoptimal, observable and consistent with thehigh dimensional framework.

L'imagerie électromagnétique est le problème de la détermination de la distribution de matériaux à partir de champs diffractés mesurés venant du domaine les contenant et sous investigation. Résoudre ce problème inverse est une tâche difficile car il est mal posé en raison de la présence d'opérateurs intégraux (de lissage) utilisés dans la représentation des champs diffractés en terme de propriétés des matériaux, et ces champs sont obtenus à un ensemble fini et non nécessairement optimal de points via des mesures bruitées. En outre, le problème inverse est non linéaire simplement en raison du fait que les champs diffractés sont des fonctions non linéaires des propriétés des matériaux. Le travail décrit traite du caractère mal posé de ce problème d'imagerie électromagnétique en utilisant des techniques de régularisation basées sur la parcimonie, qui supposent que le(s) diffracteurs(s) ne capture(nt) de fait qu'une petite fraction du domaine d'investigation. L'objectif principal est d'étudier de manière approfondie la régularisation de parcimonie pour les problèmes inverses non linéaires. Par conséquent, nous nous concentrons sur la méthode de Tikhonov non linéaire normalisée qui résout directement le problème de minimisation non linéaire en utilisant les itérations de Landweber, où une fonction de seuillage est appliquée à chaque étape pour promouvoir la contrainte de parcimonie. Ce schéma est accéléré à l'aide d'une méthode de descente de plus grande pente projetée et remplace l'opération de seuillage pour faire respecter cette contrainte. Cette approche a également été implémentée dans un domaine d'ondelettes qui permet une représentation précise de la fonction inconnue avec un nombre réduit de coefficients. En outre, nous étudions une méthode corrélée à la parcimonie qui offre de multiples solutions parcimonieuses qui partagent un support commun non nul afin de résoudre le problème non linéaire concerné. / So-called quantitative electromagnetic imaging focused onto here is the problem of determining material properties from scattered fields measured away from the domain under investigation. Solving this inverse problem is a challenging task because it is ill-posed due to the presence of (smoothing) integral operators used in the representation of scattered fields in terms of material properties, and scattered fields are obtained at a finite set of points through noisy measurements. Moreover, the inverse problem is nonlinear simply due the fact that scattered fields are nonlinear functions of the material properties. The work described in this thesis deals with the ill-posedness of the electromagnetic imaging problem using sparsity-based regularization techniques, which assume that the scatterer(s) capture only a small fraction of the investigation domain and/or can be described in sparse fashion on a certain basis. The primary aim of the thesis is to intensively investigate sparsity regularization for nonlinear inverse problems. Therefore, we focus on sparsity-regularized nonlinear Tikhonov method which directly solves the nonlinear minimization problem using Landweber iterations, where a thresholding function is applied at every iteration step to promote the sparsity constraint. This scheme is accelerated using a projected steepest descent method and replaces the thresholding operation to enforce the sparsity constraint. This approach has also been implemented in wavelet domain which allows an accurate representation of the unknown function with a reduced number of coefficients. Additionally, we investigate a method correlated with the joint sparsity which gives multiple sparse solutions that share a common nonzero support in order to solve concerned nonlinear problem.

Les performances des antennes Ultra Large Bande (ULB) les rendent appropriées pour de nombreuses applications. En radar à pénétration de surface (SPR), application visée de cette thèse, une telle bande passante offre un excellent compromis entre capacité de pénétration et résolution spatiale en imagerie micro-ondes. De plus, il a été démontré que la prise en compte du champ rayonné par l'antenne en présence de la surface améliore considérablement la qualité des images obtenues. Cette thèse aborde la problématique de la quantité de données représentant les antennes ULB. En effet, les descripteurs classiques d'antenne ne suffisent pas à caractériser l’évolution en fréquence de leurs performances. Le développement en harmoniques ou vecteurs sphériques est utilisé pour modéliser le diagramme de rayonnement d’antennes tout en réduisant le volume de données. D'autre part, les méthodes d'expansion en singularités modélisent la réponse en fréquence (ou impulsionnelle) de l'antenne par un ensemble de pôles de résonance. Le but de ce travail de thèse est d'établir un modèle compact qui représente avec précision le rayonnement d'antenne, et permette la connaissance du champ à différentes distances. A cette fin, plusieurs combinaisons des méthodes de caractérisation ont été étudiées. L'approche proposée est validée par la modélisation du diagramme de rayonnement simulé et mesuré d'une antenne Vivaldi (ETSA). Le modèle établi fournit le champ rayonné à différentes distances de l'antenne avec une erreur inférieure à 3% avec un taux de compression de 99%. La dernière partie de cette thèse présente une application de l'approche proposée au rayonnement d’antennes en présence d’interfaces / UWB antennas bandwidth makes them highly suitable for a number of applications. In surface penetrating radar (SPR) applications, which is the focus of our research, such a bandwidth range allows good signal penetration ability and fine space resolution for microwave imaging. In addition, it has been shown that the knowledge of the radiated field by the antenna enhances drastically the quality of the resulting images. The work reported in this thesis deals with the problematic of the huge amount of data representing UWB antennas. Indeed, due to the frequency dependence, the classical antenna parameters are not sufficient to characterize this type of antenna. The scalar or vector spherical wave expansion is widely used to expand the radiation pattern of a radiating antenna and permit a high compression data rate. On the other hand, the Singularity Expansion Methods are used in frequency/time domain to model the antenna response by a set of resonant poles. The purpose of this thesis is to establish a compact model representing accurately the antenna radiation characteristics, which also allows to find the field at various distances. To this end, several ways of combining the aforementioned methods have been investigated. The proposed approach is validated by modeling the simulated and measured radiation pattern of an Exponential Tapered Slot Antenna (ETSA) in free space. Furthermore, we verify that the established compact model provide radiated field at different distances from the antenna with a compression of the initial pattern up to 99% and an error below 3%. The last part of this thesis, present an application of the proposed methodology to SPR context

Le contrôle optimal stochastique (en temps discret) s'intéresse aux problèmes de décisions séquentielles sous incertitude. Les applications conduisent à des problèmes d'optimisation degrande taille. En réduisant leur taille, les méthodes de décomposition permettent le calcul numérique des solutions. Nous distinguons ici deux formes de décomposition. La emph{décomposition chaînée}, comme la Programmation Dynamique, résout successivement, des sous-problèmes de petite taille. La décomposition parallèle, comme le Progressive Hedging, consiste à résoudre itérativement et parallèlement les sous-problèmes, coordonnés par un algorithme maître. Dans la première partie de ce manuscrit, Dynamic Programming: Risk and Convexity, nous nous intéressons à la décomposition chaînée, en particulier temporelle, connue sous le nom de Programmation Dynamique. Dans le chapitre 2, nous étendons le cas traditionnel, risque-neutre, de la somme en temps des coûts, à un cadre plus général pour lequel nous établissons des résultats de cohérence temporelle. Dans le chapitre 3, nous étendons le résultat de convergence de l'algorithme SDDP (Stochastic Dual Dynamic Programming Algorithm) au cas où les fonctions de coûts (convexes) ne sont plus polyhédrales. Puis, nous nous tournons vers la décomposition parallèle, en particulier autour des méthodes de décomposition obtenues en dualisant les contraintes (contraintes spatiales presque sûres, ou de non-anticipativité). Dans la seconde partie de ce manuscrit, Duality in Stochastic Optimization, nous commençons par souligner que de telles contraintes peuvent soulever des problèmes de dualité délicats (chapitre 4).Nous établissons un résultat de dualité dans les espaces pairés $Bp{mathrm{L}^infty,mathrm{L}^1}$ au chapitre 5. Finalement, au chapitre 6, nous montrons un résultat de convergence de l'algorithme d'Uzawa dans $mathrm{L}^inftyp{Omega,cF,PP;RR^n}$, qui requière l'existence d'un multiplicateur optimal. La troisième partie de ce manuscrit, Stochastic Spatial Decomposition Methods, est consacrée à l'algorithme connu sous le nom de DADP (Dual Approximate Dynamic Programming Algorithm). Au chapitre 7, nous montrons qu'une suite de problèmes d'optimisation où une contrainte presque sûre est relaxée en une contrainte en espérance conditionnelle épi-converge vers le problème original si la suite des tribus converge vers la tribu globale. Finalement, au chapitre 8, nous présentons l'algorithme DADP, des interprétations, et des résultats de convergence basés sur la seconde partie du manuscrit / Stochastic optimal control addresses sequential decision-making under uncertainty. As applications leads to large-size optimization problems, we count on decomposition methods to tackle their mathematical analysis and their numerical resolution. We distinguish two forms of decomposition. In chained decomposition, like Dynamic Programming, the original problemis solved by means of successive smaller subproblems, solved one after theother. In parallel decomposition, like Progressive Hedging, the original problemis solved by means of parallel smaller subproblems, coordinated and updated by amaster algorithm. In the first part of this manuscript, Dynamic Programming: Risk and Convexity, we focus on chained decomposition; we address the well known time decomposition that constitutes Dynamic Programming with two questions. In Chapter 2, we extend the traditional additive in time and risk neutral setting to more general ones for which we establish time-consistency. In Chapter 3, we prove a convergence result for the Stochastic Dual Dynamic Programming Algorithm in the case where (convex) cost functions are no longer polyhedral. Then, we turn to parallel decomposition, especially decomposition methods obtained by dualizing constraints (spatial or non-anticipative). In the second part of this manuscript, Duality in Stochastic Optimization, we first point out that such constraints lead to delicate duality issues (Chapter 4).We establish a duality result in the pairing $Bp{mathrm{L}^infty,mathrm{L}^1}$ in Chapter 5. Finally, in Chapter 6, we prove the convergence of the Uzawa Algorithm in~$mathrm{L}^inftyp{Omega,cF,PP;RR^n}$.The third part of this manuscript, Stochastic Spatial Decomposition Methods, is devoted to the so-called Dual Approximate Dynamic Programming Algorithm. In Chapter 7, we prove that a sequence of relaxed optimization problems epiconverges to the original one, where almost sure constraints are replaced by weaker conditional expectation ones and that corresponding $sigma$-fields converge. In Chapter 8, we give theoretical foundations and interpretations to the Dual Approximate Dynamic Programming Algorithm

Les assemblages sont des éléments critiques pour les structures industrielles. De fortes non-linéarités de type contact frottant, ainsi que des précharges mal maîtrisées rendent complexe tout dimensionnement précis. Présents en très grand nombre sur les structures industrielles (quelques millions pour un A380), cela implique de rafiner les modèles localement et donc de gérer des problèmes numé-riques de très grandes tailles. Les nombreuses interfaces de contact frottant sont des sources de difficultés de convergence pour les simulations numériques. Il est donc nécessaire de faire appel à des méthodes robustes. Il s’agit d’utiliser des méthodes itératives de décomposition de domaine, permettant de gérer des modèles numériques extrêmement grands, couplées à des techniques adaptées afin de prendre en compte les non-linéarités de contact aux interfaces entre sous-domaines. Ces méthodes de décomposition de domaine restent encore très peu utilisées dans un cadre industriel. Des développements internes aux codes éléments finis sont souvent nécessaires et freinent ce transfert du monde académique au monde industriel.Nous proposons, dans ces travaux de thèse, une mise-en-oeuvre non intrusive de ces méthodes de décomposition de domaine : c’est-à-dire sans développement au sein du code source. En particulier, nous nous intéressons à la méthode Latin dont la philosophie est particulièrement adaptée aux problèmes non linéaires. La structure est décomposée en sous-domaines reliés entre eux au travers d’interfaces. Avec la méthode Latin, les non-linéarités sont résolues séparément des aspects linéaires. La résolution est basée sur un schéma itératif à deux directions de recherche qui font dialoguer les problèmes linéaires globaux etles problèmes locaux non linéaires.Au cours de ces années de thèse, nous avons développé un outil totalement non intrusif sous Code_Aster permettant de résoudre par une technique de décomposition de domaine mixte des problèmes d’assemblage. Les difficultés posées par le caractère mixte de la méthode Latin sont résolues par l’introduction d’une direction de recherche non locale. Des conditions de Robin sur les interfaces des sous-domaines sont alors prises en compte simplement sans modifier les sources de Code_Aster. Nous avons proposé une réécriture algébrique de l’approche multi-échelle assurant l’extensibilité de la méthode. Nous nous sommes aussi intéressés à coupler la méthode Latin en décomposition de domaine à un algorithme de Krylov. Appliqué uniquement à un problème sous-structuré avec interfaces parfaites, ce couplage permet d’accélérer la convergence. Des structures préchargées avec de nombreuses interfaces de contact frottant ont été traitées. Des simulations qui n’auraient pu être menées par un calcul direct sous Code_Aster ont été réalisées via cette stratégie de décomposition de domaine non intrusive. / Abstract : Assemblies are critical elements for industrial structures. Strong non-linearities such as frictional contact, as well as poorly controlled preloads make complex all accurate sizing. Present in large numbers on industrial structures (a few million for an A380), this involves managing numerical problems of very large size. The numerous interfaces of frictional contact are sources of difficulties of convergence for the numerical simulations. It is therefore necessary to use robust but also reliable methods. The use of iterative methods based on domain decomposition allows to manage extremely large numerical models. This needs to be coupled with adaptedtechniques in order to take into account the nonlinearities of contact at the interfaces between subdomains. These methods of domain decomposition are still scarcely used in industries. Internal developments in finite element codes are often necessary, and thus restrain this transfer from the academic world to the industrial world.In this thesis, we propose a non-intrusive implementation of these methods of domain decomposition : that is, without development within the source code. In particular, we are interested in the Latin method whose philosophy is particularly adapted to nonlinear problems. It consists in decomposing the structure into sub-domains that are connected through interfaces. With the Latin method the non-linearities are solved separately from the linear differential aspects. Then the resolution is based on an iterative scheme with two search directions that make the global linear problems and the nonlinear local problems dialogue.During this thesis, a totally non-intrusive tool was developed in Code_Aster to solve assembly problems by a mixed domain decomposition technique. The difficulties posed by the mixed aspect of the Latin method are solved by the introduction of a non-local search direction. Robin conditions on the subdomain interfaces are taken into account simply without modifying the sources of Code_Aster. We proposed an algebraic rewriting of the multi-scale approach ensuring the extensibility of the method. We were also interested in coupling the Latin method in domain decomposition to a Krylov algorithm. Applied only to a substructured problem with perfect interfaces, this coupling accelerates the convergence. Preloaded structures with numerous contact interfaces have been processed. Simulations that could not be carried out by a direct computationwith Code_Aster were performed via this non-intrusive domain decomposition strategy.

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

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

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

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.