Tesis sobre el tema "Optimisation Sans Contrainte"

Dans cette Thèse par article, nous nous intéressons au domaine de l'optimisation sans contrainte, non linéaire et différentiable. En considérant la recherche d'un optimum de la fonction f : R[indice supérieur n] [flèche vers la droite] R, on se restreint dans ce travail à chercher une racine x* de la fonction F = [triangle pointant vers le bas] f : R[indice supérieur n] [flèche vers la droite] R[indice supérieur n], c'est-à-dire un point stationnaire de la fonction f. Notre objectif a été de proposer une vision "différente" des méthodes d'ordres supérieurs. À cet effet, cette Thèse regroupera quatre articles qui soulignent le cheminement de notre travail de doctorat et la logique de notre recherche. Dans un premier article, qui servira d'introduction et de mise en contexte de cette Thèse, nous revenons sur les méthodes connues d'ordres supérieurs. Les méthodes de Newton, Chebyshev, Halley et SuperHalley ont en effet été étudiées dans différents travaux. Dans cet article, nous exhibons certaines problématiques reliées à ces méthodes : comment formuler correctement et intelligemment les méthodes utilisant des dérivées d'ordres supérieurs, comment mieux calculer leur complexité, comment vérifier leur convergence. Dans un second article, l'idée des méthodes d'ordres supérieures perçues comme directions de déplacement est proposée. En réalité, cet article exploratoire pose les bases de notre idée principale, les pistes de réflexion, les sources d'optimisme quand [i.e. quant] à l'efficacité de telles méthodes. Nous y proposons deux familles de méthodes : celle de type Halley, qui généralise et regroupe les méthodes de Halley et SuperHalley ; et celle de type Chebyshev, qui englobe et développe les algorithmes de Newton, Chebyshev, et les méthodes d'extrapolations de Jean-Pierre Dussault. Par ailleurs, dans ce chapitre, nous démontrons les propriétés de convergence (dans le cas réel) de telles méthodes et les illustrons dans un cas spécifique. Le troisième article constitue quant à lui le coeur de notre travail. Certaines pistes proposées dans le précédent article ont été abandonnées (la famille de méthode Halley) au profit d'autres plus prometteuses (la famille Chebyshev). Dans ce chapitre, nous élaborons et définissons précisément les méthodes de type Chebyshev d'ordres supérieurs. Une formulation plus globale nous permet d'y regrouper les méthodes d'extrapolations d'ordres supérieurs à 3. La convergence dans R[indice supérieur n] est démontrée (et non plus simplement dans le cas scalaire). Pour cela, nous nous appuyons sur la méthode de Shamanskii, que l'on retrouvera en fin d'article et au chapitre 4. Dans cet article, nous accordons une importance primordiale à la notion d'efficacité d'un algorithme, et en ce sens, nous définissons plus minutieusement (que la quasi-totalité des articles consultés) la notion de coût de calcul d'un algorithme. Cela nous permet de montrer que les méthodes de Chebyshev d'ordres supérieurs concurrencent les méthodes de Shamanskii (c'est-à-dire la méthode de Shamanskii à différents ordres d'itérations), connues pour être des références difficilement battables. En ce sens, plus les problèmes étudiés ont une grande taille, plus l'efficacité de nos méthodes est optimale, en comparaison avec d'autres algorithmes. La partie annexe concerne un complément, effectué dans le cadre de notre recherche. N'ayant pas été publié, nous en énoncons les résultats principaux comme piste de recherche. En effet, nos travaux ont concerné les problèmes en optimisation sans distinction autre que celle du domaine précis d'étude (des fonctions différentiables, sans contraintes, non linéaires). Or dans de nombreux cas, les problèmes que l'on cherche à minimiser ont des structures particulières : certaines fonctions ont des Hessiens creux, dont les éléments nuls sont structurés et identifiables. Autrement dit, il est concevable d'affiner nos travaux pour des cas plus spécifiques, ceux des systèmes dits "sparse". En particulier, les systèmes par bande constituent une illustration récurrente de ce type de fonctions. Nous revenons donc avec certains détails de coûts de calculs et d'efficacités de certains algorithmes présentés dans nos articles.

Dans cette thèse, nous nous intéressons à la collecte de données avec la contrainte d'énergie pour les réseaux de capteurs sans fil (RCSFs). En effet, il existe plusieurs défis qui peuvent perturber le bon fonctionnement de ce type de réseaux. Par exemple, les applications des RCSFs doivent faire face aux capacités très limitées en termes d’énergie, de mémoire et de traitement des nœuds de capteurs. De plus, à mesure que la taille de ces réseaux continue de croître, la quantité de données à traiter et à transmettre devient énorme. Dans de nombreux cas pratiques, les capteurs sans fil sont répartis sur un champ physique afin de surveiller les phénomènes physiques à forte corrélation spatio-temporelle. Par conséquent, l'objectif principal de cette thèse est de réduire la quantité de données traitées et transmises dans le scénario de collecte de données. Dans la première partie de cette thèse, nous utilisons le Compressive Sensing (CS), une technique prometteuse pour exploiter cette corrélation afin de limiter le nombre de transmissions et ainsi augmenter la durée de vie du réseau. En règle générale, nous nous intéressons à la topologie de réseau maillé, où le point de collecte de données n'est pas situé dans le rayon de communication du capteur transmetteur et des schémas de routage doivent être alors appliqués. Nous proposons le Space-Time Compressive Sensing (STCS) en exploitant conjointement la dépendance de données inter-capteurs et intra-capteur. De plus, comme le routage et le nombre de retransmissions affectent de manière significative la consommation totale d’énergie, nous introduisons le routage dans notre fonction de coût afin d’optimiser la sélection des capteurs de transmission. Les simulations montrent que cette méthode surpasse les méthodes existantes et confirment la validité de notre approche. Dans la deuxième partie de cette thèse, nous tentons de traiter un désign d’économie d’énergie presque similaire à celui proposé dans la première partie avec l’utilisation de la méthodologie de Matrix Completion (MC). Précisément, nous supposons qu'un nombre limité de nœuds de capteurs sont sélectionnés pour être actifs et représenter l'ensemble du réseau, tandis que les autres nœuds restent inactifs et ne participent pas du tout à la détection et à la transmission de leurs données. Bien que l'application d'un taux de compression des données élevé réduit considérablement la consommation d'énergie globale du réseau, la durée de vie du réseau n'est pas nécessairement prolongée en raison de l'épuisement inégal des batteries des nœuds de capteurs. A cette fin, dans la troisième partie de cette thèse, nous développons l'approche de collecte de données Energy-Aware Matrix Completion (EAMC), qui désigne les nœuds actifs en fonction de leurs niveaux d'énergies résiduelles. De plus, étant donné que nous sommes principalement intéressés par les scénarios de perte de données élevées, la quantité limitée de données fournies doit être suffisante en termes de qualité informative qu'elle détient afin d'atteindre une précision de récupération bonne et satisfaisante pour l'ensemble des données du réseau. Pour cette raison, l'EAMC sélectionne les nœuds qui peuvent représenter le mieux le réseau en fonction de leur inter-corrélation ainsi que de l'efficacité énergétique du réseau, avec l'utilisation d'une métrique combinée qui est éco-énergétique et basée sur la corrélation. Cette fonction de coût, qu'on a introduit, change avec le type d'application que l'on veut effectuer, dans le but d'atteindre une durée de vie plus longue pour le réseau
In this dissertation, we are interested in the data gathering with energy constraint for Wireless Sensor Networks (WSNs). Yet, there exist several challenges that may disturb a convenient functioning of this kind of networks. Indeed, WSNs' applications have to deal with limited energy, memory and processing capabilities of sensor nodes. Furthermore, as the size of these networks is growing continually, the amount of data for processing and transmitting becomes enormous. In many practical cases, the wireless sensors are distributed across a physical field to monitor physical phenomena with high space-time correlation. Hence, the main focus of this thesis is to reduce the amount of processed and transmitted data in the data gathering scenario. In the first part of this thesis, we consider the Compressive Sensing (CS), which is a promising technique to exploit this correlation in order to limit the number of transmission and therefore increase the lifetime of the network. Typically, we are interested in the mesh network topology, where the sink node is not in the range of sensors and routing schemes must be applied. We propose a joint Space-Time Compressive Sensing (STCS) by exploiting jointly the inter-sensors and intra-sensor data dependency. Moreover, since the routing and the number of retransmission affect significantly the total energy consumption, we introduce the routing in our cost function in order to optimize the selection of the transmitting sensors. Simulation results show that this method outperforms the existing ones and confirm the validity of our approach. In the second part of this thesis, we attempt to address nearly the same twofold energy saving scheme that is investigated in the first part with the use of the Matrix Completion (MC) methodology. Precisely, we assume that a restricted number of sensor nodes are selected to be active and represent the whole network, while the rest of nodes remain idle and do not participate at all in the data sensing and transmission. Furthermore, the set of active nodes' readings is efficiently reduced, in each time slot, according to a cluster scheduling with the Optimized Cluster-based MC data gathering approach (OCBMC). Relying on the existing MC techniques, the sink node is unable to recover the entire data matrix due to the existence of the completely empty rows that correspond to the inactive nodes. Although applying a high data compression ratio extremely reduces the overall network energy consumption, the network lifetime is not necessarily extended due to the uneven energy depletion of the sensor nodes' batteries. To this end, in the third part of this thesis, we have developed the Energy-Aware Matrix Completion based data gathering approach (EAMC), which designates the active nodes according to their residual energy levels. Furthermore, since we are mainly interested in the high data loss scenarios, the limited amount of delivered data must be sufficient in terms of informative quality it holds in order to reach good and satisfactory recovery accuracy for the entire network data. For that reason, the EAMC selects the nodes that can best represent the network depending on their inter-correlation as well as the network energy efficiency, with the use of a combined energy-aware and correlation-based metric. This introduced active node cost function changes with the type of application one wants to perform, with the intention to reach a longer lifespan for the network

Cette thèse est centrée autour de l'utilisation de la structure partiellement séparable pour l'optimisation sans contraintes, notamment pour les méthodes quasi-Newton et l'entraînement des réseaux de neurones.Une fonction partiellement séparable somme des fonctions éléments, chacune de dimension inférieure au problème total.Ainsi, le Hessian peut être agrégé en approximant séparément le hessien de chaque fonction élément par une matrice dense.Ces méthodes quasi-Newton partitionnées sont applicables aux problèmes de grandes dimensions et conservent la structure creuse du hessien, contrairement à une méthode quasi-Newton à mémoire limitée.En pratique, ces méthodes réalisent moins d'itérations qu'une méthode quasi-Newton à mémoire limitée, et sont parallélisables en distribuant les calculs reliés aux fonctions éléments.La revue de littérature complète sur le sujet a cependant révélé certaines limitations, particulièrement lorsque la dimension des fonctions éléments est large.De plus, l'unique logiciel libre d'optimisation exploitant la structure partiellement-séparable est inutilisables pour utilisateur non expérimenté, laissant pour seul choix le recourt à des logiciels commerciaux.Dans cette thèse, deux solutions sont proposées pour palier à ces lacunes ainsi qu'une application des concepts d'optimisation partiellement-séparable à l'apprentissage supervisé d'un réseau de neurones.La première contribution est une suite logicielle permettant notamment de détecter automatiquement la structure partiellement-séparable d'un problème, c'est-à-dire la récupération de chaque fonction élément de dimension réduite.Suite à cela, les structures de données partitionnées nécessaires à la mémorisation des dérivées, ou leurs approximations, sont allouées et permettent de définir des méthodes quasi-Newton partitionnées.L'ensemble est intégré à l'écosystème "JuliaSmoothOptimizers", regroupant de nombreux outils pour l'optimisation lisse, dont des algorithmes d'optimisation pouvant exploiter la séparabilité partielle détectée.La seconde contribution remplace l'approximation d'un hessien élément par une matrice dense par un opérateur linéaire quasi-Newton à mémoire limitée.Ce faisant, le coût mémoire de l'approximation totale du hessien n'est plus relié quadratiquement à la dimension des fonctions éléments.Une méthode quasi-Newton partitionnée à mémoire limitée est alors applicable lorsque les fonctions éléments sont de grandes tailles.Chaque méthode quasi-Newton partitionnée à mémoire limitée possède une preuve convergence globale.De plus, les résultats numériques montrent que ces méthodes surpassent les méthodes quasi-Newton partitionnées ou à mémoire limitées lorsque les éléments sont de grandes tailles.La dernière contribution étudie l'exploitation de la structure partiellement-séparable lors l'entraînement supervisé d'un réseau de neurones.Le problème d'optimisation lié à l'entraînement n'est généralement pas partiellement-séparable.Dès lors, une fonction de perte partiellement-séparable ainsi qu'une architecture de réseau partitionnée sont introduites afin de rendre l'entraînement partiellement-séparable.Les résultats numériques combinant ces deux apports sont compétitifs avec des architectures et des fonctions de perte standards selon les méthodes d'entraînement de l'état de l'art.De surcroît, cette combinaison permet un schéma de parallélisation supplémentaire aux méthodes déjà existantes pour l'apprentissage supervisé.En effet, les calculs de chaque fonction de perte élément peuvent être distribués à un travailleur nécessitant seulement une fraction du réseau de neurones pour opérer.Finalement, un entraînement quasi-Newton partitionnée à mémoire limitée est proposé.Cet entrainement est montré empiriquement comme compétitif avec les méthodes d'entraînement de l'état de l'art
This thesis studies and improves the use of the partially-separable structure for unconstrained optimization, particularly for quasi-Newton methods and training neural networks.A partially-separable function is the sum of element functions, each of lower dimension than the total problem.Thus, the Hessian can be aggregated by separately approximating the Hessian of each element function with a dense matrix.These partitioned quasi-Newton methods are applicable to high-dimensional problems and maintain the sparse structure of the Hessian, unlike a limited-memory quasi-Newton method.In practice, these methods require fewer iterations than a limited-memory quasi-Newton method and are parallelizable by distributing computations related to the element functions.However, a comprehensive literature review on the subject has revealed some limitations, particularly when the dimension of the element functions is large.Additionally, the only open-source optimization software exploiting the partially-separable structure is unusable for inexperienced users, leaving only commercial software as an option.In this thesis, two solutions are proposed to address these shortcomings, along with an application of partially-separable optimization concepts to supervised learning of a neural network.The first contribution is a software suite based on an automatic detection of the partially-separable structure of a problem, i.e., retrieves each reduced-dimensional element function.Following this, partitioned data structures necessary for storing derivatives, or their approximations, are allocated and used to define partitioned quasi-Newton optimization methods.The entire suite is integrated into the "JuliaSmoothOptimizers" ecosystem, which gathers numerous tools for smooth optimization, including optimization algorithms that can therefore exploit the detected partial separability.The second contribution replaces the approximation of an element Hessian by a dense matrix with a limited-memory quasi-Newton linear operator.As a result, the memory cost of the total Hessian approximation is no longer quadratically related to the dimension of the element functions.A limited-memory partitioned quasi-Newton method is then applicable when the element functions are large.Each limited-memory partitioned quasi-Newton method has a proof of global convergence.Additionally, numerical results show that these methods outperform partitioned or limited-memory quasi-Newton methods when the elements are large.The final contribution examines the exploitation of the partially-separable structure during supervised training of a neural network.The optimization problem associated with training is generally not partially-separable.Therefore, a partially-separable loss function and a partitioned network architecture are introduced to make the training partially-separable.Numerical results combining these two contributions are competitive with standard architectures and loss functions according to state-of-the-art training methods.Moreover, this combination produces an additional parallelization scheme to existing methods for supervised learning.Indeed, the calculations of each element loss function can be distributed to a worker requiring only a fraction of the neural network to operate.Finally, a limited-memory partitioned quasi-Newton training is proposed.This training is empirically shown to be competitive with state-of-the-art training methods

La réduction des coûts de production des cellules photovoltaïques et l'augmentation de leur rendement de conversion présentent aujourd’hui un fort intérêt technologique et écologique pour répondre aux problèmes de changement climatique engendrés par les énergies fossiles (charbon, pétrole et gaz naturel). La motivation de cette thèse est l’étude des procédés innovants de production de couches ultra-minces de silicium monocristallin de plusieurs centaines de nanomètres à plusieurs dizaines de micromètres d’épaisseur, basés sur les contraintes thermiques et l’implantation d’hydrogène à basse énergie. Le détachement des couches ultra-minces de silicium se fait sans perte de matière première, permettant ainsi de réduire la consommation du silicium afin de produire des cellules photovoltaïques à bas-coûts.Dans ce travail, nous avons tout d’abord déterminé par modélisation analytique et numérique les contraintes permettant le détachement du silicium par contraintes induites « Controlled-Spalling » et prédit l’épaisseur détachée des couches minces de silicium. Les modèles proposés dépendent des paramètres thermiques et élastiques des matériaux utilisés et de chargement thermique appliqué. Un bon accord entre les résultats théoriques et expérimentaux a été obtenu. Nous avons ensuite étudié les paramètres optimaux conduisant au détachement des films de silicium, à savoir l’épaisseur et la nature du substrat contraignant ainsi que l’épaisseur de la colle. Par la suite, des essais de détachement du silicium par contraintes induites guidé par l’implantation d’hydrogène ont été réalisés. Des caractérisations expérimentales et des simulations FEM des contraintes thermiques induites dans le silicium implanté à différents stades de recuits ont été faites permettant de comprendre les mécanismes mis en jeu lors du détachement du silicium fragilisé. Ensuite, des mesures par différentes techniques (Spectroscopie Raman, Profilomètre optique, MEB, Microscope optique numérique) des contraintes résiduelles et de la rugosité des films détachés par le procédé « Controlled-Spalling » ont été réalisées pour explorer les pistes conduisant à l’amélioration de la qualité de ces films
The reduction of photovoltaic cells cost and the increase of their efficiency is probably one of the best solution to tacle the climate change issues. The mean of this thesis is to study the innovative processes to produce ultra-thin monocrystalline silicon layers without loss of raw material (with thicknesses ranging from several hundred nanometers to several micrometers), by using thermal stress and low energy hydrogen implantation. The use of such kerf-free processes leads to a significant reduction of the silicon consumption, in order to produce of low-cost photovoltaic solar cells.In this work, by using analytical and numerical modeling, we first determined the thermal stresses needed for the detachment of silicon by stress-induced spalling process and predicts the detached thickness of silicon foils. These models depend on thermals and elastics parameters of metal used as well as the applied thermal loading. A good agreement between the theoretical and experimental results was obtained. Furthermore, different optimal parameters leading to the detachment of silicon foils with desired thicknesses using SIS process were investigated such as the thickness of the stressor layer, the nature of stressor layer and the thickness of glue. In a second part, thin silicon layers were transferred as a function of thermal annealing using the stress-induced spalling process guided by hydrogen implantation-induced defects. Then, the use of experimental characterizations and FEM simulations of the thermal stresses induced in implanted silicon we explain the mechanisms involved when combining the two processes. Characterization of silicon foils was performed by various technique in order to validate and optimized the process

Cette thèse développe des méthodes de diagonalisation conjointe de matrices et de tenseurs d’ordre trois, et son application à la séparation MIMO de sources de télécommunications numériques. Après un état, les motivations et objectifs de la thèse sont présentés. Les problèmes de la diagonalisation conjointe et de la séparation de sources sont définis et un lien entre ces deux domaines est établi. Par la suite, plusieurs algorithmes itératifs de type Jacobi reposant sur une paramétrisation LU sont développés. Pour chacun des algorithmes, on propose de déterminer les matrices permettant de diagonaliser l’ensemble considéré par l’optimisation d’un critère inverse. On envisage la minimisation du critère selon deux approches : la première, de manière directe, et la seconde, en supposant que les éléments de l’ensemble considéré sont quasiment diagonaux. En ce qui concerne l’estimation des différents paramètres du problème, deux stratégies sont mises en œuvre : l’une consistant à estimer tous les paramètres indépendamment et l’autre reposant sur l’estimation indépendante de couples de paramètres spécifiquement choisis. Ainsi, nous proposons trois algorithmes pour la diagonalisation conjointe de matrices complexes symétriques ou hermitiennes et deux algorithmes pour la diagonalisation conjointe d’ensembles de tenseurs symétriques ou non-symétriques ou admettant une décomposition INDSCAL. Nous montrons aussi le lien existant entre la diagonalisation conjointe de tenseurs d’ordre trois et la décomposition canonique polyadique d’un tenseur d’ordre quatre, puis nous comparons les algorithmes développés à différentes méthodes de la littérature. Le bon comportement des algorithmes proposés est illustré au moyen de simulations numériques. Puis, ils sont validés dans le cadre de la séparation de sources de télécommunications numériques
This thesis develops joint diagonalization of matrices and third-order tensors methods for MIMO source separation in the field of digital telecommunications. After a state of the art, the motivations and the objectives are presented. Then the joint diagonalisation and the blind source separation issues are defined and a link between both fields is established. Thereafter, five Jacobi-like iterative algorithms based on an LU parameterization are developed. For each of them, we propose to derive the diagonalization matrix by optimizing an inverse criterion. Two ways are investigated : minimizing the criterion in a direct way or assuming that the elements from the considered set are almost diagonal. Regarding the parameters derivation, two strategies are implemented : one consists in estimating each parameter independently, the other consists in the independent derivation of couple of well-chosen parameters. Hence, we propose three algorithms for the joint diagonalization of symmetric complex matrices or hermitian ones. The first one relies on searching for the roots of the criterion derivative, the second one relies on a minor eigenvector research and the last one relies on a gradient descent method enhanced by computation of the optimal adaptation step. In the framework of joint diagonalization of symmetric, INDSCAL or non symmetric third-order tensors, we have developed two algorithms. For each of them, the parameters derivation is done by computing the roots of the considered criterion derivative. We also show the link between the joint diagonalization of a third-order tensor set and the canonical polyadic decomposition of a fourth-order tensor. We confront both methods through numerical simulations. The good behavior of the proposed algorithms is illustrated by means of computing simulations. Finally, they are applied to the source separation of digital telecommunication signals

Les modèles graphiques définissent une famille de formalismes et d'algorithmes utilisés en particulier pour le raisonnement logique et probabiliste, dans des domaines aussi variés que l'analyse d'image ou le traitement du langage naturel. Ils sont capables d'être appris à partir de données, donnant une information probabiliste qui peut ensuite être combinée avec des informations logiques. Le but de la thèse est d'améliorer l'efficacité des algorithmes de raisonnement sur ces modèles croisant probabilités et logique en généralisant un mécanisme fondamental des outils de raisonnement purement logique parmi les plus efficaces (solveurs SAT) à ce cas hybride mêlant probabilités et logique: l'apprentissage dirigé par les conflits. Les travaux s'appuient sur le concept de dualité en programmation linéaire et conduisent à un apprentissage sans conflit de contraintes linéaires bénéficiant d'un traitement particulier efficace issu de la résolution d'un problème de sac à dos
Graphical models define a family of formalisms and algorithms used in particular for logical and probabilistic reasoning, in fields as varied as image analysis or natural language processing. They are capable of being learned from data, giving probabilistic information that can then be combined with logical information. The goal of the thesis is to improve the efficiency of reasoning algorithms on these models crossing probabilities and logic by generalizing a fundamental mechanism of the most efficient purely logical reasoning tools (SAT solvers) to this hybrid case mixing probabilities and logic: conflict-based learning. The work is based on the concept of duality in linear programming and our learning mechanism is conflict-free, producing linear constraints efficiently solved using a knapsack formulation

Durant ces dernières années, de nombreux travaux de recherches ont été menés dans le domaine des réseaux multi-sauts sans fil à contraintes (MWNs: Multihop Wireless Networks). Grâce à l'évolution de la technologie des systèmes mico-electro-méchaniques (MEMS) et, depuis peu, les nanotechnologies, les MWNs sont une solution de choix pour une variété de problèmes. Le principal avantage de ces réseaux est leur faible coût de production qui permet de développer des applications ayant un unique cycle de vie. Cependant, si le coût de fabrication des nœuds constituant ce type de réseaux est assez faible, ces nœuds sont aussi limités en capacité en termes de: rayon de transmission radio, bande passante, puissance de calcul, mémoire, énergie, etc. Ainsi, les applications qui visent l'utilisation des MWNs doivent être conçues avec une grande précaution, et plus spécialement la conception de la fonction de routage, vu que les communications radio constituent la tâche la plus consommatrice d'énergie.Le but de cette thèse est d'analyser les différents défis et contraintes qui régissent la conception d'applications utilisant les MWNs. Ces contraintes se répartissent tout le long de la pile protocolaire. On trouve au niveau application des contraintes comme: la qualité de service, la tolérance aux pannes, le modèle de livraison de données au niveau application, etc. Au niveau réseau, on peut citer les problèmes de la dynamicité de la topologie réseau, la présence de trous, la mobilité, etc. Nos contributions dans cette thèse sont centrées sur l'optimisation de la fonction de routage en considérant les besoins de l'application et les contraintes du réseau. Premièrement, nous avons proposé un protocole de routage multi-chemin "en ligne" pour les applications orientées QoS utilisant des réseaux de capteurs multimédia. Ce protocole repose sur la construction de multiples chemins durant la transmission des paquets vers leur destination, c'est-à-dire sans découverte et construction des routes préalables. En permettant des transmissions parallèles, ce protocole améliore la transmission de bout-en-bout en maximisant la bande passante du chemin agrégé et en minimisant les délais. Ainsi, il permet de répondre aux exigences des applications orientées QoS.Deuxièmement, nous avons traité le problème du routage dans les réseaux mobiles tolérants aux délais. Nous avons commencé par étudier la connectivité intermittente entre les différents et nous avons extrait un modèle pour les contacts dans le but pouvoir prédire les future contacts entre les nœuds. En se basant sur ce modèle, nous avons proposé un protocole de routage, qui met à profit la position géographique des nœuds, leurs trajectoires, et la prédiction des futurs contacts dans le but d'améliorer les décisions de routage. Le protocole proposé permet la réduction des délais de bout-en-bout tout en utilisant d'une manière efficace les ressources limitées des nœuds que ce soit en termes de mémoire (pour le stockage des messages dans les files d'attentes) ou la puissance de calcul (pour l'exécution de l'algorithme de prédiction).Finalement, nous avons proposé un mécanisme de contrôle de la topologie avec un algorithme de routage des paquets pour les applications orientés évènement et qui utilisent des réseaux de capteurs sans fil statiques. Le contrôle de la topologie est réalisé à travers l'utilisation d'un algorithme distribué pour l'ordonnancement du cycle de service (sleep/awake). Les paramètres de l'algorithme proposé peuvent être réglés et ajustés en fonction de la taille du voisinage actif désiré (le nombre moyen de voisin actifs pour chaque nœud). Le mécanisme proposé assure un compromis entre le délai pour la notification d'un événement et la consommation d'énergie globale dans le réseau
Great research efforts have been carried out in the field of challenged multihop wireless networks (MWNs). Thanks to the evolution of the Micro-Electro-Mechanical Systems (MEMS) technology and nanotechnologies, multihop wireless networks have been the solution of choice for a plethora of problems. The main advantage of these networks is their low manufacturing cost that permits one-time application lifecycle. However, if nodes are low-costly to produce, they are also less capable in terms of radio range, bandwidth, processing power, memory, energy, etc. Thus, applications need to be carefully designed and especially the routing task because radio communication is the most energy-consuming functionality and energy is the main issue for challenged multihop wireless networks.The aim of this thesis is to analyse the different challenges that govern the design of challenged multihop wireless networks such as applications challenges in terms of quality of service (QoS), fault-tolerance, data delivery model, etc., but also networking challenges in terms of dynamic network topology, topology voids, etc. Our contributions in this thesis focus on the optimization of routing under different application requirements and network constraints. First, we propose an online multipath routing protocol for QoS-based applications using wireless multimedia sensor networks. The proposed protocol relies on the construction of multiple paths while transmitting data packets to their destination, i.e. without prior topology discovery and path establishment. This protocol achieves parallel transmissions and enhances the end-to-end transmission by maximizing path bandwidth and minimizing the delays, and thus meets the requirements of QoS-based applications. Second, we tackle the problem of routing in mobile delay-tolerant networks by studying the intermittent connectivity of nodes and deriving a contact model in order to forecast future nodes' contacts. Based upon this contact model, we propose a routing protocol that makes use of nodes' locations, nodes' trajectories, and inter-node contact prediction in order to perform forwarding decisions. The proposed routing protocol achieves low end-to-end delays while using efficiently constrained nodes' resources in terms of memory (packet queue occupancy) and processing power (forecasting algorithm). Finally, we present a topology control mechanism along a packet forwarding algorithm for event-driven applications using stationary wireless sensor networks. Topology control is achieved by using a distributed duty-cycle scheduling algorithm. Algorithm parameters can be tuned according to the desired node's awake neighbourhood size. The proposed topology control mechanism ensures trade-off between event-reporting delay and energy consumption

L'optimisation intervient dans de nombreuses applications IFPEN, notamment dans l'estimation de paramètres de modèles numériques à partir de données en géosciences ou en calibration des moteurs. Dans ces applications, on cherche à minimiser une fonction complexe, coûteuse à estimer, et dont les dérivées ne sont pas toujours disponibles. A ces difficultés s'ajoutent la prise en compte de contraintes non linéaires et parfois l'aspect multi-objectifs. Au cours de cette thèse, nous avons développé la méthode SQA (Sequential Quadradic Approximation), une extension de la méthode d'optimisation sans dérivées de M.J.D. Powell pour la prise en compte de contraintes à dérivées connues ou non. Cette méthode est basée sur la résolution de problèmes d'optimisation simplifiés basés sur des modèles quadratiques interpolant la fonction et les contraintes sans dérivées, construits à partir d'un nombre limité d'évaluations de celles-ci. Si la résolution de ce sous-problème ne permet pas une progression pour l'optimisation originale, de nouvelles simulations sont réalisées pour tenter d'améliorer les modèles. Les résultats de SQA sur différents benchmarks montrent son efficacité pour l'optimisation sans dérivées sous contraintes. Enfin, SQA a été appliqué avec succès à deux applications industrielles en ingénierie de réservoir et en calibration des moteurs. Une autre problématique majeure en optimisation étudiée dans cette thèse est la minimisation multi-objectifs sous contraintes. La méthode évolutionnaire Multi-Objective Covariance Matrix Adaptation, adaptée à la prise en compte des contraintes, s'est révélée très performante dans l'obtention de compromis pour la calibration des moteurs.

Depuis ces deux dernières décennies, une nouvelle technologie sans fil appelée Réseau de Capteur Sans Fil (RCSF) résultant d"une fusion entre les systèmes embarqués et les communications sans fil a vu le jour. Un RCSF ("WSN : Wireless Sensor Network" en Anglais) est un réseau Ad hoc composé d"un grand nombre de nœuds qui sont des micro-capteurs qui peuvent être déployés de façon aléatoire ou déterministe dans une zone d"intérêt donnée. Ces nœuds capteurs sont capables de récolter plusieurs paramètres physiques sur l"environnement qui les entoure, appelé généralement zone de captage (ou zone de surveillance). Ensuite, ils doivent si nécessaire traiter les données capturées et les transmettre à un (ou plusieurs) nœud de collecte appelé station de base, centre de traitement ("sink" en Anglais). Beaucoup de domaines d"applications tels que le contrôle et suivi environnemental, le contrôle de production dans l"industrie, la surveillance de zone, le monitoring de l"habitat, l"agriculture intelligente, etc. sont basés sur les RCSF. Toutefois, les RCSF ne sont pas parfaits. En effet, compte tenu de leur petite taille, leur faible coût et leurs déploiement dans des zones souvent hostiles ou difficiles d"accès, les nœuds capteurs présentent un certain nombre de faiblesses parmi lesquelles une durée de vie du réseau limitée, une bande passante faible, des capacités de capture et de communication réduites, etc. Afin de surmonter ces contraintes des RCSF, plusieurs problématiques de recherche sont nées ces dernières années, et les principales portent sur l"optimisation de la consommation énergétique en vue d"améliorer la durée de vie du réseau. D"autres recherches importantes menées dans le domaine de ces réseaux portent sur les stratégies de placement des nœuds, sur la couverture de zones et sur la connectivité du réseau. Cependant, la plupart des solutions proposées ces dernières années ne prennent pas en compte toutes ces problématiques dans leurs modèles de résolution ; alors que dans beaucoup d"applications des RCSF telles que la surveillance de zone critique, le monitoring de l"habitat, l"agriculture intelligente, il est nécessaire de garantir en même temps une couverture complète de la zone de surveillance, une bonne connectivité du réseau, tout en optimisant au mieux la durée de vie de celui-ci. Le but de cette thèse est donc de proposer de nouveaux mécanismes efficaces pour l"optimisation de la durée de vie dans les RCSF, tout en garantissant, à tout moment de cette durée de vie, une couverture totale de la zone de surveillance, ainsi qu"une bonne connectivité du réseau. Pour atteindre nos objectifs, nous avons étudié et fait des propositions dans deux axes qui sont le placement des nœuds et les mécanismes d"ordonnancement au niveau de la couche MAC. Pour ces derniers, nous avons mis en place un algorithme appelé DSMAC (Distributed Scheduling Medium Acces Control) qui est basé sur notre méthode de placement des nœuds. Par ailleurs, DSMAC permet de couvrir 100% de la zone de surveillance, assure une bonne connectivité du RCSF et permet également aux nœuds capteurs d"économiser jusqu"à 30% de leur énergie comparativement à d"autres protocoles MAC tels que TunableMAC
Since the past two decades, a new technology called Wireless Sensor Network (WSN) which result in a fusion of embedded systems and wireless communications has emerged. A WSN is Ad hoc network composed of many sensors nodes communicating via wireless links and which can be deployed randomly or deterministically over a given interest region. Theses sensors can also collect data from the environment, do local processing and transmit the data to a sink node or Base Station (BS) via multipath routing. Thereby, a wide range of potential applications have been envisioned using WSN such as environmental conditions monitoring, wildlife habitat monitoring, industrial diagnostic, agricultural, improve health care, etc. Nevertheless,WSN are not perfect. Indeed, given their small size, their low cost and their deployment generally in hostile or difficult access areas, sensor nodes have some weaknesses such as: a limited energy, so a network lifetime limited, limited bandwidth, limited computations and communications capabilities, etc. To overcome these limitations, several research issues from were created in recent years, and the main issues focus on the optimization of energy consumption in order to improve the network lifetime. Other important researches focus on issues of coverage areas, placement strategies of sensor nodes and network connectivity. However, most solutions proposed in recent years to resolve these issues do not take into account all these issues that we cited above in resolutions models; while in many WSN applications such as monitoring critical region, wildlife habitat monitoring, agricultural application, a full coverage of the monitoring region and network connectivity are mandatory as well an energy-awareness network lifetime. The objective of this thesis is thus to propose new scheduling mechanisms for optimizing the network lifetime in WSN, while ensuring at any time of the network lifetime a full coverage of the monitored region and network connectivity. To achieve our goals, we have study and done proposal in two axes which are placement strategy of sensor nodes and scheduling mechanism in the MAC layer. For these, we have implemented a Distributed Scheduling Medium Access Control algorithm (DSMAC) based on our placement method. Furthermore, DSMAC enables to cover 100% of the monitored region, to ensure optimal network connectivity and also allows sensors node to save up to 30% of their energy compared to other MAC protocols such as TunableMAC

Ce travail a pour contexte des applications industrielles où des mobiles communiquent via un réseau local sans fil. Nous avons élaboré une plate-forme où des mobiles collaborent via un réseau IEEE802. 11 en mode infrastructure, les communications s'effectuent via des points d'accès (AP) auxquels les mobiles sont affiliés. Chaque AP gère une zone appelée cellule, les mobiles vont être à passer d'une cellule à une autre et s'affilier à différents AP. Ce mécanisme, appelé Handover génère un trafic de gestion, qui va perturber le trafic de collaboration des mobiles, et a un coût en temps pendant lequel le mobile va être isolé du réseau. Ces effets peuvent être désastreux dans des applications où le temps est un facteur critique. Nous proposons des solutions efficaces qui agissent sur la phase de recherche d'un nouvel AP, qui réduisent le trafic de gestion du handover et qui peuvent complétées par l'ajout d'une deuxième interface réseau sur chaque mobile

Ce travail a pour contexte des applications industrielles où des mobiles communiquent via un réseau local sans fil. Nous avons élaboré une plate-forme où des mobiles collaborent via un réseau IEEE802.11 en mode infrastructure, les communications s'effectuent via des points d'accès (AP) auxquels les mobiles sont affiliés. Chaque AP gère une zone appelée cellule, les mobiles vont être à passer d'une cellule à une autre et s'affilier à différents AP. Ce mécanisme, appelé Handover génère un trafic de gestion, qui va perturber le trafic de collaboration des mobiles, et a un coût en temps pendant lequel le mobile va être isolé du réseau. Ces effets peuvent être désastreux dans des applications où le temps est un facteur critique. Nous proposons des solutions efficaces qui agissent sur la phase de recherche d'un nouvel AP, qui réduisent le trafic de gestion du handover et qui peuvent complétées par l'ajout d'une deuxième interface réseau sur chaque mobile

Le développement simultané de terminaux mobiles multimédia (smartphones, tablettes) et de réseaux d'accès offrant des débits élevés conduit à une explosion du trafic liés aux contenus multimédia. Cette croissance nécessite un partage efficace des ressources radio entre fournisseurs de contenus (dans le cas de la diffusion) ou entre récepteurs (dans le cas de services de vidéo à la demande). Cette thèse propose des outils de partage équitable des ressources en termes de qualité des contenus multimédia reçu et de délai de transmission dans les deux contextes précédents. La variété des compromis débit-distorsion des contenus multimédia est exploitée à cet effet. Dans un premier temps, une solution centralisée de contrôle conjoint du débit de codage et de transmission de plusieurs programmes transmis sur un même canal est considérée. L'objectif est de fournir des flux de qualités similaires avec des variations limitées, tout en assurant des délais de transmission comparables. Ce problème est résolu en synthétisant une commande prédictive à l'aide d'outils d'optimisation sous contrainte. Dans un second temps, seule l'allocation de bande est centralisée, le contrôle des caractéristiques de compression de chaque flux est réalisé de manière distribuée. Le contrôleur centralisé ne renvoie que le niveau de remplissage des tampons associés à chaque flux aux fournisseurs de contenus distants. Une stratégie de régulation des débits de codage est alors mise en place par ces fournisseurs, de manière à réguler le niveau en bits ou en image des tampons. La stabilité de ce système de régulation couplé est étudiée en détails. Enfin, l'optimisation inter-couches d'une chaine de transmission de contenus multimédia scalable est considérée. Ce problème est formulé dans le contexte de la programmation dynamique. Lorsque des modèles de complexité raisonnable sont considérés et avec des caractéristiques du système bien connues, des solutions optimales peuvent être obtenues. Des techniques d'apprentissage sont mises en œuvre, lorsque le système n'est que partiellement connu, par exemple, lorsque l'état du canal de transmission parvient avec du retard à l'organe de commande.

Bon nombre de problèmes d'optimisation rencontrés dans l'industrie font appel à des systèmes complexes et n'ont pas de formulation analytique explicite : ce sont des problèmes d'optimisation de type boîte noire (ou blackbox en anglais). Ils peuvent être dits “mixtes”, auquel cas ils impliquent des variables de différentes natures (continues et discrètes), et avoir de nombreuses contraintes à satisfaire. De plus, les évaluations de l'objectif et des contraintes peuvent être numériquement coûteuses.Dans cette thèse, nous étudions des méthodes de résolution de tels problèmes complexes, à savoir des problèmes d'optimisation boîte noire avec contraintes et variables mixtes, pour lesquels les évaluations des fonctions sont très coûteuses en temps de calcul.Puisque l'utilisation de dérivées n'est pas envisageable, ce type de problèmes est généralement abordé par des approches sans dérivées comme les algorithmes évolutionnaires, les méthodes de recherche directe et les approches basées sur des métamodèles.Nous étudions les performances de telles méthodes déterministes et stochastiques dans le cadre de l'optimisation boîte noire, y compris sur un cas test en éléments finis que nous avons conçu. En particulier, nous évaluons les performances de la variante ORTHOMADS de l'algorithme de recherche directe MADS sur des problèmes d'optimisation continus et à variables mixtes issus de la littérature.Nous proposons également une nouvelle méthode d'optimisation boîte noire, nommée BOA, basée sur des approximations par métamodèles. Elle comporte deux phases dont la première vise à trouver un point réalisable tandis que la seconde améliore itérativement la valeur de l'objectif de la meilleure solution réalisable trouvée. Nous décrivons des expériences utilisant des instances de la littérature et des applications de l'industrie automobile. Elles incluent des tests de notre algorithme avec différents types de métamodèles, ainsi que des comparaisons avec ORTHOMADS
Numerous industrial optimization problems are concerned with complex systems and have no explicit analytical formulation, that is they are blackbox optimization problems. They may be mixed, namely involve different types of variables (continuous and discrete), and comprise many constraints that must be satisfied. In addition, the objective and constraint blackbox functions may be computationally expensive to evaluate.In this thesis, we investigate solution methods for such challenging problems, i.e constrained mixed-variable blackbox optimization problems involving computationally expensive functions.As the use of derivatives is impractical, problems of this form are commonly tackled using derivative-free approaches such as evolutionary algorithms, direct search and surrogate-based methods.We investigate the performance of such deterministic and stochastic methods in the context of blackbox optimization, including a finite element test case designed for our research purposes. In particular, the performance of the ORTHOMADS instantiation of the direct search MADS algorithm is analyzed on continuous and mixed-integer optimization problems from the literature.We also propose a new blackbox optimization algorithm, called BOA, based on surrogate approximations. It proceeds in two phases, the first of which focuses on finding a feasible solution, while the second one iteratively improves the objective value of the best feasible solution found. Experiments on instances stemming from the literature and applications from the automotive industry are reported. They namely include results of our algorithm considering different types of surrogates and comparisons with ORTHOMADS

Dans cette thèse, nous nous sommes intéressés à la résolution exacte de problèmes de dimensionnement de réseaux RCSF, rencontrés pendant la phase de planification. Tout d’abord nous nous intéressons au problème de déploiement. Il s’agit de positionner les capteurs dans un plan euclidien afin de minimiser le coût des opérations de communication pour transmettre les données vers le Station de Base. Le deuxième problème, le problème de configuration de réseau, s’intéresse à l’organisation des capteurs dans des zones/clusters. L’objectif ici est de déterminer le nombre optimal de zones et leurs portées respectives afin de minimiser la consommation en énergie de chaque capteur. Les méthodes proposées sont basées sur des algorithmes de programmation dynamique qui garantissent des solutions optimales et sont à faible complexité si on les compare aux approches de littérature. Le dernier problème étudié concerne l’affectation de puissances aux capteurs et d’ordonnancement des transmissions. Ici l’objectif est de garantir les transmissions concurrentes entre les nœuds tout en minimisant le temps de transmission des données. Au cœur de notre approche est la stratégie d’affectation de puissances de transmissions qui tente de maximiser la valeur minimale de SINR estimée chez les récepteurs. Le problème est modélisé et résolu en utilisant un algorithme itératif basé sur la programmation linéaire
In this thesis, we focused on the development of optimal methods regarding WSN dimensioning problems, mostly encountered during the planning phase. These were instantiated basically into three combinatorial optimization problems. The network deployment scheme which seeks to place the sensors in a such way that the cost of communication operations is minimized. The network configuration problem that asks to find a strategy for dividing the network such that some criteria are satisfied. In the problem’s model we took into account the data aggregation constraint and the discrete values of power transmission. For both problems we proposed a resolution method, based on dynamic programming, which permitted us to solve them optimally. Finally, the joint problem of scheduling and power assignment, consisted in finding a feasible scheduling under SINR constraints and a power assignment scheme to guarantee successful concurrent transmissions. As the problem is shown to be NP-hard we propose a greedy heuristic. The resolution method for the power assignment strategy, an iterative algorithm based on linear programming, provides optimal solutions

L'optimisation sans dérivées (OSD) a connu un regain d'intérêt ces dernières années, principalement motivée par le besoin croissant de résoudre les problèmes d'optimisation définis par des fonctions dont les valeurs sont calculées par simulation (par exemple, la conception technique, la restauration d'images médicales ou de nappes phréatiques). Ces dernières années, un certain nombre de méthodes d'optimisation sans dérivée ont été développées et en particulier des méthodes fondées sur un modèle de région de confiance se sont avérées obtenir de bons résultats. Dans cette thèse, nous présentons un nouvel algorithme de région de confiance, basé sur l'interpolation, qui se montre efficace et globalement convergent (en ce sens que sa convergence vers un point stationnaire est garantie depuis tout point de départ arbitraire). Le nouvel algorithme repose sur la technique d'auto-correction de la géométrie proposé par Scheinberg and Toint (2010). Dans leur théorie, ils ont fait avancer la compréhension du rôle de la géométrie dans les méthodes d'OSD à base de modèles. Dans notre travail, nous avons pu améliorer considérablement l'efficacité de leur méthode, tout en maintenant ses bonnes propriétés de convergence. De plus, nous examinons l'influence de différents types de modèles d'interpolation sur les performances du nouvel algorithme. Nous avons en outre étendu cette méthode pour prendre en compte les contraintes de borne par l'application d'une stratégie d'activation. Considérer une méthode avec ensemble actif pour l'optimisation basée sur des modèles d'interpolation donne la possibilité d'économiser une quantité importante d'évaluations de fonctions. Il permet de maintenir les ensembles d'interpolation plus petits tout en poursuivant l'optimisation dans des sous-espaces de dimension inférieure. L'algorithme résultant montre un comportement numérique très compétitif. Nous présentons des résultats sur un ensemble de problèmes-tests issu de la collection CUTEr et comparons notre méthode à des algorithmes de référence appartenant à différentes classes de méthodes d'OSD. Pour réaliser des expériences numériques qui intègrent le bruit, nous créons un ensemble de cas-tests bruités en ajoutant des perturbations à l'ensemble des problèmes sans bruit. Le choix des problèmes bruités a été guidé par le désir d'imiter les problèmes d'optimisation basés sur la simulation. Enfin, nous présentons des résultats sur une application réelle d'un problème de conception de forme d'une aile fourni par Airbus.

Ce mémoire se veut d'abord un recueil des principales variantes de l'algorithme optimal en pire cas pour la résolution de problèmes convexes et fortement convexes sans contraintes présenté par Yurii Nesterov en 1983 et en 2004. Ces variantes seront présentées dans un cadre unifié et analysées de manière théorique et empirique. On y retrouve une analyse des rôles des différents paramètres composant l'algorithme de base ainsi que de l'influence des constantes L et mu, respectivement la constante de Lipschitz du gradient et la constante de forte convexité de la fonction objectif, sur le comportement des algorithmes. On présentera également une nouvelle variante hybride et nous démontrerons empiriquement qu'elle performe mieux que plusieurs variantes dans la majorité des situations. La comparaison empirique des différentes variantes sur des problèmes sans contraintes utilise un modèle de calcul se basant sur le nombre d'appels à un oracle de premier ordre plutôt que sur le nombre d'itérations. Enfin, une application de ces variantes sur trois instances de problèmes en imagerie numérique ainsi qu'une analyse empirique des résultats obtenus en confrontation avec la méthode optimale FISTA et l'algorithme classique L-BFGS-B viennent clore ce mémoire.

L’optimisation sans dérivées (OSD) a connu un regain d’intérêt ces dernières années, principalement motivée par le besoin croissant de résoudre les problèmes d’optimisation définis par des fonctions dont les valeurs sont calculées par simulation (par exemple, la conception technique, la restauration d’images médicales ou de nappes phréatiques).Ces dernières années, un certain nombre de méthodes d’optimisation sans dérivée ont été développées et en particulier des méthodes fondées sur un modèle de région de confiance se sont avérées obtenir de bons résultats.Dans cette thèse, nous présentons un nouvel algorithme de région de confiance, basé sur l’interpolation, qui se montre efficace et globalement convergent (en ce sens que sa convergence vers un point stationnaire est garantie depuis tout point de départ arbitraire). Le nouvel algorithme repose sur la technique d’auto-correction de la géométrie proposé par Scheinberg and Toint (2010). Dans leur théorie, ils ont fait avancer la compréhension du rôle de la géométrie dans les méthodes d’OSD à base de modèles. Dans notre travail, nous avons pu améliorer considérablement l’efficacité de leur méthode, tout en maintenant ses bonnes propriétés de convergence. De plus, nous examinons l’influence de différents types de modèles d’interpolation sur les performances du nouvel algorithme.Nous avons en outre étendu cette méthode pour prendre en compte les contraintes de borne par l’application d’une stratégie d’activation. Considérer une méthode avec ensemble actif pour l’optimisation basée sur des modèles d’interpolation donne la possibilité d’économiser une quantité importante d’évaluations de fonctions. Il permet de maintenir les ensembles d’interpolation plus petits tout en poursuivant l’optimisation dans des sous-espaces de dimension inférieure. L’algorithme résultant montre un comportement numérique très compétitif. Nous présentons des résultats sur un ensemble de problèmes-tests issu de la collection CUTEr et comparons notre méthode à des algorithmes de référence appartenant à différentes classes de méthodes d’OSD.Pour réaliser des expériences numériques qui intègrent le bruit, nous créons un ensemble de cas-tests bruités en ajoutant des perturbations à l’ensemble des problèmes sans bruit. Le choix des problèmes bruités a été guidé par le désir d’imiter les problèmes d’optimisation basés sur la simulation. Enfin, nous présentons des résultats sur une application réelle d’un problème de conception de forme d’une aile fourni par Airbus
Derivative-free optimization (DFO) has enjoyed renewed interest over the past years, mostly motivated by the ever growing need to solve optimization problems defined by functions whose values are computed by simulation (e.g. engineering design, medical image restoration or groundwater supply).In the last few years, a number of derivative-free optimization methods have been developed and especially model-based trust-region methods have been shown to perform well.In this thesis, we present a new interpolation-based trust-region algorithm which shows to be efficient and globally convergent (in the sense that its convergence is guaranteed to a stationary point from arbitrary starting points). The new algorithm relies on the technique of self-correcting geometry proposed by Scheinberg and Toint [128] in 2009. In their theory, they advanced the understanding of the role of geometry in model-based DFO methods, in our work, we improve the efficiency of their method while maintaining its good theoretical convergence properties. We further examine the influence of different types of interpolation models on the performance of the new algorithm.Furthermore, we extended this method to handle bound constraints by applying an active-set strategy. Considering an active-set method in bound-constrained model-based optimization creates the opportunity of saving a substantial amount of function evaluations. It allows to maintain smaller interpolation sets while proceeding optimization in lower dimensional subspaces. The resulting algorithm is shown to be numerically highly competitive. We present results on a test set of smooth problems from the CUTEr collection and compare to well-known state-of-the-art packages from different classes of DFO methods.To report numerical experiments incorporating noise, we create a test set of noisy problems by adding perturbations to the set of smooth problems. The choice of noisy problems was guided by a desire to mimic simulation-based optimization problems. Finally, we will present results on a real-life application of a wing-shape design problem provided by Airbus

La propulsion hybride (thermique-électrique) constitue une solution pertinente dans la conception de véhicules consommant moins de 2 litres de carburant / 100 km. Néanmoins, ce type de motorisation se heurte à des niveaux de coûts trop élevés pour une large diffusion. Une des raisons de ces coûts importants se situe au niveau des aimants permanents de type terre-rare intégrant la constitution de la machine électrique, et dont le cours des prix est très instable, rendant ce type de machine difficilement compatible avec le marché visé. L'objectif de cette thèse est d’investiguer les structures de machines électriques sans aimant terre-rare et dont les performances massiques peuvent rester comparables à celles des machines à aimants permanents. La première partie des travaux correspond à une vaste étude bibliographique sur les différentes technologies de machines électriques, les différentes architectures et topologies existantes, les matériaux innovants et enfin les techniques et méthode d’analyse et d’optimisation. A la fin de cette phase, il est fait le choix d’étudier les machines synchro-réluctantes à barrières de flux. L’accent est alors mis sur le design de la géométrie du rotor, mais également sur l’impact des matériaux utilisés (matériaux magnétiques classiques ou innovants) sur les performances. La seconde partie de la thèse a pour objectif de mettre en œuvre une stratégie efficace afin de dimensionner de manière optimale l’architecture de la machine choisie. Le choix est fait d’aborder le problème de manière séquentielle : en premier lieu, une optimisation de la topologie seule en s’affranchissant de l’impact de la commande ; dans un deuxième temps, une optimisation de la commande de la géométrie optimisée avec tracé des cartographies de performances ; enfin, une évaluation des différents matériaux au travers de la comparaison de ces performances. Trois configurations de machines sont dimensionnées : une machine synchro-réluctante classique à air (SyRC), une machine synchro-réluctante assistée de d’aimants permanents de type ferrites (SyRA) et enfin une machine synchro-réluctante utilisant le matériau dit « Dual Phase » (SyRDP). Celui-ci présente théoriquement la caractéristique de pourvoir changer localement ses propriétés magnétiques (passage des propriétés magnétiques d’un acier vers celles amagnétiques de l’air dans le cas limite idéal) grâce à un traitement thermique particulier, tout en conservant ses propriétés mécaniques. Cette étude permet de conclure que la machine synchro-réluctante assistée de ferrites montre les meilleures aptitudes, tant pour ce qui est de la puissance crête que du défluxage potentiel. Cependant, la machine synchro-réluctante dans cette configuration est sur le plan mécanique plus fragile que la SyRC et la SyRDP. En effet, avec l’ajout des ferrites, les ponts fer (magnétiques) permettant d’assurer l’intégrité mécanique du rotor à vitesse élevée sont d’autant plus sollicités. En phase de conception, l’optimisation électromagnétique tend à les réduire car ce sont des courts-circuits magnétiques entrainant une réduction des performances, alors que les considérations mécaniques tendent plutôt à augmenter leur épaisseur. La troisième partie de cette thèse porte sur la prise en compte des contraintes mécaniques lors du dimensionnement électromagnétique du rotor. Etant donné que la modélisation et l’optimisation électromagnétiques sont basées sur des modèles éléments finis, et afin de ne pas alourdir davantage le dimensionnement, il est décidé de mettre en place un modèle analytique des contraintes mécaniques particulièrement critiques dans les ponts magnétiques. Les équations de calcul sont inspirées de la théorie des poutres et le modèle est recalibré grâce à des simulations éléments finis
Hybrid propulsion (electric thermal) is a relevant solution in the search for vehicles consuming less than 2 liters of fuel / 100 km. Nevertheless, this type of motorization comes up against cost levels that are too high for widespread distribution. One of the reasons for these high costs is the level of permanent magnets integrating the constitution of the electric machine. In addition, the "material cost" of these permanent magnets has soared in recent years making this type of machine difficult to match the target market. The aim of the thesis is to propose a magnetless electrical machine structure whose mass performances are comparable to those of permanent magnet machines. This increase in performance can be achieved by high rotation speeds or thermal sizing different from those usually used. The works proposed as part of this thesis will be as follows: - In-depth bibliographic analysis to propose a structure and a principle most adapted to the envisaged constraints- Proposal of a multi physical model (magnetic, thermal, mechanical) of the selected structure. - Use of the multi-physical model for optimal sizing- Follow-up of the realization of the prototype - Experimental validation of the prototype. This work will be conducted as part of a consortium integrating academics, manufacturers and automotive suppliers of the highest order

La gestion de l’énergie est une préoccupation majeure dans les réseaux de capteurs sans fil. Ces capteurs sont généralement alimentés par une batterie embarquant une quantité d’énergie finie. Par conséquent, le temps pendant lequel les capteurs peuvent surveiller une zone et communiquer par signaux radio peut être limitée lorsqu’il n’est pas possible de remplacer leur batterie. En outre, les réseaux de capteurs sont parfois déployés dans les zones difficiles d’accès ou dans des environnements hostiles dans lesquels le placement des capteurs peut être considéré comme aléatoire (c’est le cas par exemple lorsque les capteurs sont largués d’un avion ou d’un hélicoptère). Ainsi, l’emplacement des capteurs n’est pas connu a priori et les approches pour utiliser efficacement l’énergie sont nécessaires. Cette thèse explore l’utilisation de la génération colonnes pour optimiser l’utilisation de l’énergie dans les réseaux de capteurs sans fil. La génération de colonnes peut être vue comme un cadre général pour résoudre différents problèmes dans la conception et l’exploitation de ces réseaux. Plusieurs versions du problème et divers modèles sont proposés pour représenter leur fonctionnement,en utilisant notamment la génération de colonnes. Ces approches exploitent le caractère naturel de la génération de colonnes pour modéliser les différents aspects des réseaux de capteurs sans fil.Dans cette thèse, des contributions algorithmiques sont apportées afin de tirer le meilleur parti de la génération de colonnes au plan de l’efficacité computationnelle. Des stratégies hybrides combinant génération de colonnes et (méta)-heuristiques et donnant lieu à des méthodes exactes et approchées sont proposées et évaluées. Des tests numériques montrent l’efficacité des approches proposées et des bornes supérieures qui peuvent être employées pour évaluer l’efficacité des méthodes centralisées et distribuées. Enfin, des perspectives sont dégagées concernant les performances et la portabilité de la génération de colonnes pour aborder des problèmes plus réalistes et tenir compte des caractéristiques des réseaux de capteurs sans fil du futur
Energy is a major concern in wireless sensor networks (WSN). These devices are typically battery operated and provided with a limited amount of energy. As a consequence, the time during which sensors can monitor the interesting phenomena and communicate through wireless signals might be limited because of (sometimes) irreplaceable batteries. Additionally, it is very common for WSN to be usedin remote or hostile environments which possibly makes necessary a random placement strategy (by using an airplane, a drone or a helicopter). Hence, the sensors location is not known a priori and approaches to efficiently use the energy are needed to answer to network topologies only known after sensors deployment. This thesis explores the use of column generation to efficiently use the energy in WSN. It is shown that column generation can be used as a general framework to tackle different problems in WSN design. Several versions of the problem and models for the operation of the WNS are adapted to be solved through column generation. These approaches take advantage of the natural way that column generation offers to consider different features of the WSN operation. Additionally, some computational improvements are proposed to keep the column generation method operating as an efficient exact approach. Hybrid strategies combining column generation with (meta)heuristic and exact approaches are considered and evaluated. The computational experiments demonstrate the efficiency of the proposed approaches and provide practitioners on WSN research with strategies to compute upper bounds to evaluate heuristic centralized and decentralized approaches. Finally, some future directions of research are provided based on the performance and adaptability of column generation to consider more sophisticated models and characteristics newly introduced in sensor devices

Cette thèse porte sur la commande des systèmes non linéaires soumis à des contraintes non différentiables ou non convexes. L'objectif est de pouvoir réaliser une commande permettant de considérer tout type de contraintes évaluables en temps réel.Pour répondre à cet objectif, la commande prédictive a été utilisée en ajoutant des fonctions barrières à la fonction de coût. Un algorithme d'optimisation sans gradient a permis de résoudre ce problème d'optimisation. De plus, une formulation permettant de garantir la stabilité et la robustesse vis-à-vis de perturbations a été proposée dans le cadre des systèmes linéaires. La démonstration de la stabilité repose sur les ensembles invariants et la théorie de Lyapunov.Dans le cas des systèmes non linéaires, les réseaux de neurones dynamiques ont été utilisés comme modèle de prédiction pour la commande prédictive. L'apprentissage de ces réseaux ainsi que les observateurs non linéaires nécessaires à leur utilisation ont été étudiés. Enfin, notre étude s'est portée sur l'amélioration de la prédiction par réseaux de neurones en présence de perturbations.La méthode de synthèse de correcteurs présentée dans ces travaux a été appliquée à l’évitement d’obstacles par un véhicule autonome
This PhD thesis deals with the control of nonlinear systems subject to nondifferentiable or nonconvex constraints. The objective is to design a control law considering any type of constraints that can be online evaluated.To achieve this goal, model predictive control has been used in addition to barrier functions included in the cost function. A gradient-free optimization algorithm has been used to solve this optimization problem. Besides, a cost function formulation has been proposed to ensure stability and robustness against disturbances for linear systems. The proof of stability is based on invariant sets and the Lyapunov theory.In the case of nonlinear systems, dynamic neural networks have been used as a predictor for model predictive control. Machine learning algorithms and the nonlinear observers required for the use of neural networks have been studied. Finally, our study has focused on improving neural network prediction in the presence of disturbances.The synthesis method presented in this work has been applied to obstacle avoidance by an autonomous vehicle

Cette thèse a pour objectif la proposition de nouvelles approches algorithmiques et de modélisation pour la résolution de certains problèmes d’optimisation de réseau dans les domaines des transports et des télécommunications. Plus précisément, les problèmes étudiés tombent dans le domaine du transport aérien, nommément le problème d’affectation des niveaux de vol dans l’espace aérienne, et dans le domaine des télécommunications où on traite des problèmes d’allocation de ressources dans les réseaux 5G. Un aspect important qui a été pris en compte dans cette étude est l’incertitude des données, c’est-à-dire le fait qu’une partie des données d’entrée ne sont pas connues de façon précise. Notre tâche a consisté à modéliser chacun des problèmes, proposer une formulation compacte des variantes déterministe et robuste, et proposer des approches appropriées pour les résoudre. Les problèmes étudiés tombent dans la catégorie des problèmes NP-complets et ils sont difficile à résoudre même pour des instances de taille modeste. Ils deviennent encore plus difficiles dans leur version robuste. Pour le problème d’affectation des niveaux de vols, nous avons considéré les incertitudes liées à l’heure de départ qui sont modélisées via un modèle de mélange gaussien. Le problème est modélisé comme un « chance-constrained problem » et résolu par un algorithme heuristique de génération de contraintes. Il s’agit d’une approche générale qui trouvera des applications plus large que ceux étudiés dans cette thèse. Ensuite, nous avons étudié la conception optimale des réseaux sans fil de 5ème génération (5G) dans le contexte de l’architectures Superfluid. Plus précisément, l’architecture 5G Superfluid est basée sur des entités de réseau appelées « Bloc Fonctionnel Réutilisable » (RFB) qui sont à la base des réseaux 5G. Nous avons étudié le problème de conception d’un tel réseau Superfluid à coût minimum pour lequel une formulation en programme linéaire mixte suivie d’une approche de résolution utilisant la décomposition de Benders a été implémentée ont été proposées. Enfin, le problème spécifique de conception de réseaux virtuels a été considéré sous l’angle de l’efficacité énergétique. Nous avons proposé une formulation de programmation linéaire en nombres entiers mixte du problème robuste, et présentons une nouvelle matheuristique basée sur la combinaison d’un algorithme génétique avec la recherche de voisinage. Les résultats numériques ont porté sur des instances de taille réalistes et ont montré la validité des modèles et des approches proposées
This Ph.D. Thesis is focused on proposing new optimization modeling and algorithmic approaches for dealing with real-world network optimization problems arising in the transportation and telecommunications fields. Since the focus has been on real-world applications, a relevant aspect that has been taken into account is data uncertainty, i.e. the fact that the value of a subset of input data of the problem is not exactly known when the problem is solved. More precisely, in the context of transportation problems, it was considered the flight level assignment problem, which arises in air traffic management. It aims at establishing the flight levels of a set of aircraft in order to improve the total assignment revenue, to reduce the total number of flight conflicts and also the total en-route delay. In this context, we proposed a new chance-constrained optimization problem and iterative constraint-generation heuristic which is based on both analytical and sampling methods. Besides transportation problems, this Thesis has also focused on the optimal design of 5th generation of wireless networks (5G) considering Superfluid and virtual architectures. Specifically, the 5G Superfluid architecture is based on atomic virtual entities called Reusable Functional Block (RFB). We investigated the problem of minimizing the total installation costs of a 5G Superfluid network (composed of virtual entities and realized over a physical network) while guaranteeing constraint on user coverage, downlink traffic performance and technical constraints on RFBs of different nature. To solve this hard problem, we proposed a Benders decomposition approach. Concerning instead the design of general virtual networks, we adopted a green paradigm that pursues energy-efficiency and tackled a state-of-the-art robust mixed integer linear programming formulation of the problem, by means of a new matheuris tic based on combining a genetic algorithm with exact large neighborhood searches. Results of computational tests executed considering realistic problem instances have shown the validity of all the new optimization modeling and algorithmic approaches proposed in this Thesis for the transportation and telecommunications problems sketched above

Le nombre important de véhicules sur le réseau routier peut entraîner des problèmes d'encombrement et de sécurité. Les usagers des réseaux routiers qui nous intéressent sont les camionneurs qui transportent des marchandises, pouvant rouler avec des véhicules non conformes ou emprunter des routes interdites pour gagner du temps. Le transport de matières dangereuses est réglementé et certains lieux, surtout les ponts et les tunnels, leur sont interdits d'accès. Pour aider à faire appliquer les lois en vigueur, il existe un système de contrôles routiers composé de structures fixes et de patrouilles mobiles. Le déploiement stratégique de ces ressources de contrôle mise sur la connaissance du comportement des camionneurs que nous allons étudier à travers l'analyse de leurs choix de routes. Un problème de choix de routes peut se modéliser en utilisant la théorie des choix discrets, elle-même fondée sur la théorie de l'utilité aléatoire. Traiter ce type de problème avec cette théorie est complexe. Les modèles que nous utiliserons sont tels, que nous serons amenés à faire face à des problèmes de corrélation, puisque plusieurs routes partagent probablement des arcs. De plus, puisque nous travaillons sur le réseau routier du Québec, le choix de routes peut se faire parmi un ensemble de routes dont le nombre est potentiellement infini si on considère celles ayant des boucles. Enfin, l'étude des choix faits par un humain n'est pas triviale. Avec l'aide du modèle de choix de routes retenu, nous pourrons calculer une expression de la probabilité qu'une route soit prise par le camionneur. Nous avons abordé cette étude du comportement en commençant par un travail de description des données collectées. Le questionnaire utilisé par les contrôleurs permet de collecter des données concernant les camionneurs, leurs véhicules et le lieu du contrôle. La description des données observées est une étape essentielle, car elle permet de présenter clairement à un analyste potentiel ce qui est accessible pour étudier les comportements des camionneurs. Les données observées lors d'un contrôle constitueront ce que nous appellerons une observation. Avec les attributs du réseau, il sera possible de modéliser le réseau routier du Québec. Une sélection de certains attributs permettra de spécifier la fonction d'utilité et par conséquent la fonction permettant de calculer les probabilités de choix de routes par un camionneur. Il devient alors possible d'étudier un comportement en se basant sur des observations. Celles provenant du terrain ne nous donnent pas suffisamment d'information actuellement et même en spécifiant bien un modèle, l'estimation des paramètres n'est pas possible. Cette dernière est basée sur la méthode du maximum de vraisemblance. Nous avons l'outil, mais il nous manque la matière première que sont les observations, pour continuer l'étude. L'idée est de poursuivre avec des observations de synthèse. Nous ferons des estimations avec des observations complètes puis, pour se rapprocher des conditions réelles, nous continuerons avec des observations partielles. Ceci constitue d'ailleurs un défi majeur. Nous proposons pour ces dernières, de nous servir des résultats des travaux de (Bierlaire et Frejinger, 2008) en les combinant avec ceux de (Fosgerau, Frejinger et Karlström, 2013). Bien qu'elles soient de nature synthétiques, les observations que nous utilisons nous mèneront à des résultats tels, que nous serons en mesure de fournir une proposition concrète qui pourrait aider à optimiser les décisions des responsables des contrôles routiers. En effet, nous avons réussi à estimer, sur le réseau réel du Québec, avec un seuil de signification de 0,05 les valeurs des paramètres d'un modèle de choix de routes discrets, même lorsque les observations sont partielles. Ces résultats donneront lieu à des recommandations sur les changements à faire dans le questionnaire permettant de collecter des données.
Using transportation roads enables workers to reach their work facilities. Security and traffic jam issues are all the more important given that the number of vehicles is always increasing and we will focus on merchandise transporters in this study. Dangerous items transportation is under strict control as it is for example forbidden for them to be carried through a tunnel or across a bridge. Some transporters may drive a vehicle that has defects or/and they may be ta\-king some forbidden roads so as to reach their destination faster. Transportation of goods is regulated by the law and there exists a control system, whose purpose is to detect frauds and to make sure controlled vehicles are in order. The strategic deployment of control resources can be based on the knowledge of transporters behaviour, which is going to be studied through their route choice analysis. The number of routes can be unbounded especially if we consider loops, which leads to a complex problem to be solved. We can also mention issues closely related to route choice problem using discrete choice models such as correlation between routes sharing links and point out the fact that human decision process is not considered something easy. A route choice problem can be modelled based on the random utility theory and as a consequence we will focus on the discrete choice models. We are going to use such model on the real road network of Quebec and we will derive an expression of the probability, for a transporter, to pick one route. We are going to explain the way we did our study. It started first by doing a data description job as we are convinced this is a step that will help other analysts to have a clear view of the data situation. Some data are network related and the corresponding attributes collected will be used to model the road network of Quebec. We will use some attributes to explain the utility function, which leads to the definition of the function that gives the probability that a user takes a given route. Once this function is fully specified, the behaviour study can be done, except that we have a set of observations that are absolutely incomplete. When observations are a gathering of data collected during a road control, the information they provide us is not enough and thus, the parameters estimation will fail. We might seem blocked but in fact, we brought the idea of using simulated observations. We are going to estimate model parameters with firstly complete observations and in order to imitate the real conditions, we then are going to use partial observations. This constitutes a main challenge and we overcome it by using the results presented in (Bierlaire et Frejinger, 2008) combined with those from (Fosgerau, Frejinger et Karlström, 2013). We will demonstrate that even though the observations used are simulated, we will deliver conclusions that can be useful for road network managers. The main results we provide in this work is that estimation can be done with a 0,05 signification level on real road network of Quebec, while the observations are incomplete. Eventually, our results should motivate network managers to improve the set of questions they use to collect data as it would help them to strengthen their knowledge about the merchandise transporters and hopefully, the decision process will lead to optimized resource deployments.