Notre société étant plus dépendante que jamais au vecteur électrique, la moindre perturbation du transport ou de l’acheminement de l’électricité a un impact social et économique important. La fiabilité et la sécurité des réseaux électriques sont donc cruciales pour les gestionnaires de réseaux, en plus des aspects économiques. De plus, les réseaux de transport sont interconnectés pour réduire les coûts des opérations et pour améliorer la sécurité. Un des plus grand défis des gestionnaires des réseaux de transport est ainsi de se coordonner avec les réseaux voisins, ce qui soulève des problèmes liés à la taille du problème, à l’interopérabilité et à la confidentialité des données.Cette thèse se focalise principalement sur la sécurité des opérations sur les réseaux électriques, c’est pourquoi l’évolution des principales caractéristiques des blackouts, qui sont des échecs de la sécurité des réseaux, sont étudiés sur la période 2005-2016. L’approche de cette étude consiste à déterminer quelles sont les principales caractéristiques des incidents de ces 10 dernières années, afin d’identifier ce qui devrait être intégré pour réduire le risque que ces incidents se reproduisent. L’évolution a été étudiée et comparé avec les caractéristiques des blackouts qui se sont produit avant 2005. L’étude se focalise sur les préconditions qui ont mené à ces blackouts et sur les cascades, et particulièrement sur le rôle de la vitesse des cascades. Les caractéristiques importante sont extraites et intégrées dans la suite de notre travail.Un algorithme résolvant un problème préventif d’Optimal Power Flow avec contraintes de sécurité (SCOPF) de manière distribuée est ainsi développé. Ce problème consiste en l’ajout de contraintes qui assure qu’après la perte de n’importe quel appareil d’importance, le nouveau point d’équilibre, atteint suite au réglage primaire en fréquence, respecte les contraintes du système. L’algorithme développé utilise une décomposition fine du problème et est implémenté sous le paradigme multi-agent, basé sur deux catégories d’agents : les appareils et les bus. Les agents sont coordonnés grâce à l’ « Alternating Direction Method of Multipliers (ADMM)» et grâce à un problème de consensus. Cette décomposition procure l’autonomie et la confidentialité nécessaire aux différents acteurs du système, mais aussi, un bon passage à l’échelle par rapport à la taille du problème. Cet algorithme a aussi pour avantage d’être robuste à n’importe quelle perturbation, incluant la séparation du système en plusieurs régions.Puis, pour prendre en compte l’incertitude sur la production créée par les erreurs de prédiction des fermes éoliennes, une approche distribuée à deux étapes est développée pour résoudre un problème d’Optimal Power Flow avec contraintes probabilistes (CCOPF), d’une manière complétement distribuée. Les erreurs de prédiction des fermes éoliennes sont modélisées par des lois normales indépendantes et les écarts par rapport aux plannings de production sont considérés compensés par le réglage primaire en fréquence. La première étape de l’algorithme a pour but de déterminer des paramètres de sensibilités nécessaires pour formuler le problème. Les résultats de cette étape sont ensuite des paramètres d’entrée de la seconde étape qui, elle, résout le problème de CCOPF. Une extension de cette formulation permet d’ajouter de la flexibilité au problème en permettant la réduction de la production éolienne. Cet algorithme est basé sur la même décomposition fine que précédemment où les agents sont également coordonnés par l’ADMM et grâce à un problème de consensus. En conclusion, cet algorithme en deux étapes garantit la confidentialité et l’autonomie des différents acteurs, et est parallèle et adaptée aux plateformes hautes performances. / Our societies are more dependent on electricity than ever, thus any disturbance in the power transmission and delivery has major economic and social impact. The reliability and security of power systems are then crucial to keep, for power system operators, in addition to minimizing the system operating cost. Moreover, transmission systems are interconnected to decrease the cost of operation and improve the system security. One of the main challenges for transmission system operators is therefore to coordinate with interconnected power systems, which raises scalability, interoperability and privacy issues. Hence, this thesis is concerned with how TSOs can operate their networks in a decentralized way but coordinating their operation with other neighboring TSOs to find a cost-effective scheduling that is globally secure.The main focus of this thesis is the security of power systems, this is why the evolution of the main characteristics of the blackouts that are failures in power system security, of the period 2005-2016 is studied. The approach consists in determining what the major characteristics of the incidents of the past 10 years are, to identify what should be taken into account to mitigate the risk of incidents. The evolution have been studied and compared with the characteristics of the blackouts before 2005. The study focuses on the pre-conditions that led to those blackouts and on the cascades, and especially the role of the cascade speed. Some important features are extracted and later integrated in our work.An algorithm that solve the preventive Security Constrained Optimal Power Flow (SCOPF) problem in a fully distributed manner, is thus developed. The preventive SCOPF problem consists in adding constraints that ensure that, after the loss of any major device of the system, the new steady-state reached, as a result of the primary frequency control, does not violate any constraint. The developed algorithm uses a fine-grained decomposition and is implemented under the multi-agent system paradigm based on two categories of agents: devices and buses. The agents are coordinated with the Alternating Direction method of multipliers in conjunction with a consensus problem. This decomposition provides the autonomy and privacy to the different actors of the system and the fine-grained decomposition allows to take the most of the decomposition and provides a good scalability regarding the size of the problem. This algorithm also have the advantage of being robust to any disturbance of the system, including the separation of the system into regions.Then, to account for the uncertainty of production brought by wind farms forecast error, a two-step distributed approach is developed to solve the Chance-Constrained Optimal Power Flow problem, in a fully distributed manner. The wind farms forecast errors are modeled by independent Gaussian distributions and the mismatches with the initials are assumed to be compensated by the primary frequency response of generators. The first step of this algorithm aims at determining the sensitivity factors of the system, needed to formulate the problem. The results of this first step are inputs of the second step that is the CCOPF. An extension of this formulation provides more flexibility to the problem and consists in including the possibility to curtail the wind farms. This algorithm relies on the same fine-grained decomposition where the agents are again coordinated by the ADMM and a consensus problem. In conclusion, this two-step algorithm ensures the privacy and autonomy of the different system actors and it is de facto parallel and adapted to high performance platforms.

Avec l'importance que prend le parc de véhicules électriques rechargeable (VER) depuis ces dix dernières années et au vu de l'important taux de croissance le caractérisant, se pose alors la question de l'infrastructure de recharge y inhérente. Une manière d'en tirer bénéfice et d'en minimiser l'impact consistera en l'agrégation en flotte et de gérer cette dernière en conséquence. L'objectif général de la thèse est de proposer et de développer des algorithmes décentralisés qui permettront de minimiser les impacts les plus critiques attendus d'une forte pénétration de VERs. La prise en compte de la réversibilité des chargeurs actuels et de leur fonctionnement sur les quatre quadrants, les algorithmes proposés, rendent également possible la fourniture de services système au réseau ; cependant il faut aussi tenir compte du caractère aléatoire de plusieurs variables telles que les heures d'arrivée te de départ des véhicules considérés, de l'état de charge initial entre autres. Cette thèse introduit d'abord une approche globale et une optimisation locale afin d'établir un benchmark solide à des fins d'évaluation des techniques développées dans ce travail. Vient ensuite ce qui est la contribution majeure représentée par deux méthodologies d'optimisation lesquelles sont basées sur la théorie des jeux évolutionniste. Toutes les deux techniques introduisent la notion d'équité dans la répartition des tâches et des ressources entre VERs et donnent plus de poids aux contraintes liées au rôle de l'usager/propriétaire du véhicule et de son implication dans la gestion de la demande. En outre, l'une de ces méthodes comprend des solutions de rechange pour intégrer la charge rapide dans le processus de planification, tandis que l'autre méthode permet au VER de fournir des services auxiliaires comme le remplissage des creux de demande, l'effacement de la pointe le pic de rasage, active, d'équilibrer la puissance active ou encore de fournir de l'énergie réactive. / With a stock of Plug-in electric vehicles (PEVs) under continuous grow during the last ten years, concerns have been raised in terms of their charging infrastructure and their integration into the electricity distribution systems. If PEVs are considered as a fleet, both their impact and benefit for the electrical power system can be substantial. The general objective of this thesis is to propose and develop decentralized algorithms allowing to mitigate the most critical impacts expected to occur with the integration of PEVs. Taking into account the reversibility of chargers, the proposed algorithms are intended to consider re-injection of energy, in order to provide ancillary services to the grid. Moreover, algorithms are supposed to consider the stochastic nature of variables like the arrival and departure of PEVs, their initial state of charge, among others. Under these premises and taking into account earlier contributions, this thesis introduces a centralized approach and a distributed optimization approach in order to have a solid benchmark for the justification of the most elaborate contributions of the last part of this work. After these first experiences, the most important contribution of this thesis is represented in two decentralized optimization methodologies that were developed in details based on concepts of evolutionary game theory. Both of them introduce the concept of fairness in the allocation of tasks and resources among PEVs, and give more weight to social constraints represented on the role of PEV owners in the load managing process. Furthermore, one of these methodologies includes alternatives to integrate fast charging rates in the scheduling process, while the other methodology allows PEVs to provide ancillary services like valley filling, peak shaving, active and reactive power balancing, and reactive power supply.

Cette thèse s'intéresse au problème d'estimation et d'optimisation distribuée dans les réseaux asynchrones, c'est à dire en n'utilisant que des communications locales et asynchrones. A partir de multiples applications allant de l'apprentissage automatique aux réseaux de capteurs sans-fils, nous concevons et analysons théoriquement de nouveaux algorithmes résolvant trois problèmes de nature très différentes : la propagation de la plus grande des valeurs initiales, l'estimation de leur moyenne et enfin l'optimisation distribuée.

Les protocoles de consensus ont gagné beaucoup d’intérêt ces dernières années. Dans cette thèse, nous étudions les problèmes d’optimisation, de contrôle, et de théorie de jeu qui se posent dans ces protocoles. Tout d’abord, nous étudions les techniques d’optimisation pour des problèmes de sélection de poids permettant ainsi d’augmenter la vitesse de convergence de protocoles de consensus dans les réseaux. Nous proposons de sélectionner les poids en appliquant un algorithme d’approximation: minimisation de la norme p de Schatten de la matrice de poids. Nous caractérisons l’erreur induite par cette approximation et nous montrons que l’algorithme proposé a l’avantage qu’il peut être soit résolu de façon distribuée. Ensuite, nous proposons un cadre conceptuel d’analyse des jeux d’adversaire qui peut ajouter du bruit aux poids utilisés par l’algorithme de consensus de moyenne afin d’éloigner le système de consensus. Nous analysons également la performance des algorithmes de consensus de moyenne où les informations échangées entre les agents voisins sont soumises à la quantification uniforme déterministe (les valeurs réelles envoyées par les nœuds de leurs voisins sont tronquées). Le problème de la terminaison des protocoles de consensus s’avère difficile dans le cadre distribué. Nous proposons un algorithme distribué pour la terminaison des protocoles de consensus. L’algorithme réduit la charge de communication tout en garantissant la convergence vers un consensus. Enfin, nous proposons une mesure de similarité qui évalue la qualité d’un regroupement (clustering) des nœuds dans un réseau. Un algorithme local de clustering basé sur cette métrique est donné. / Consensus protocols have gained a lot of interest in the recent years. In this thesis, we study optimization, control, and game theoretical problems arising in consensus protocols. First, we study optimization techniques for weight selection problems to increase the speed of convergence of discrete-time consensus protocols on networks. We propose to select the weights by applying an approximation algorithm: minimizing the Schatten p-norm of the weight matrix. We characterize the approximation error and we show that the proposed algorithm has the advantage that it can be solved in a totally distributed way. Then we propose a game theoretical framework for an adversary that can add noise to the weights used by averaging protocols to drive the system away from consensus. We give the optimal strategies for the game players (the adversary and the network designer) and we show that a saddle-point equilibrium exists in mixed strategies. We also analyze the performance of distributed averaging algorithms where the information exchanged between neighboring agents is subject to deterministic uniform quantization (e.g., when real values sent by nodes to their neighbors are truncated). Consensus algorithms require that nodes exchange messages persistently to reach asymptotically consensus. We propose a distributed algorithm that reduces the communication overhead while still guaranteeing convergence to consensus. Finally, we propose a score metric that evaluates the quality of clusters such that the faster the random walk mixes in the cluster and the slower it escapes, the higher is the score. A local clustering algorithm based on this metric is proposed.

L'apprentissage des matrices de rang faible est un problème de grande importance dans les statistiques, l'apprentissage automatique, la vision par ordinateur et les systèmes de recommandation. En raison de sa nature NP-difficile, une des approches principales consiste à résoudre sa relaxation convexe la plus étroite : la minimisation de la norme de trace. Parmi les différents algorithmes capables de résoudre cette optimisation, on peut citer la méthode de Frank-Wolfe, particulièrement adaptée aux matrices de grande dimension. En préparation à l'utilisation d'infrastructures distribuées pour accélérer le calcul, cette étude vise à explorer la possibilité d'exécuter l'algorithme de Frank-Wolfe dans un réseau en étoile avec le modèle BSP (Bulk Synchronous Parallel) et à étudier son efficacité théorique et empirique. Concernant l'aspect théorique, cette étude revisite le taux de convergence déterministe de Frank-Wolfe et l'étend à des cas non déterministes. En particulier, il montre qu'avec le sous-problème linéaire résolu de manière appropriée, Frank-Wolfe peut atteindre un taux de convergence sous-linéaire à la fois en espérance et avec une probabilité élevée. Cette contribution pose la fondation théorique de l'utilisation de la méthode de la puissance itérée ou de l'algorithme de Lanczos pour résoudre le sous-problème linéaire de Frank-Wolfe associé à la minimisation de la norme de trace. Concernant l'aspect algorithmique, dans le cadre de BSP, cette étude propose et analyse quatre stratégies pour le sous-problème linéaire ainsi que des méthodes pour la recherche linéaire. En outre, remarquant la propriété de mise à jour de rang-1 de Frank-Wolfe, il met à jour le gradient de manière récursive, avec une représentation dense ou de rang faible, au lieu de le recalculer de manière répétée à partir de zéro. Toutes ces conceptions sont génériques et s'appliquent à toutes les infrastructures distribuées compatibles avec le modèle BSP. Concernant l'aspect empirique, cette étude teste les conceptions algorithmiques proposées dans un cluster Apache SPARK. Selon les résultats des expériences, pour le sous-problème linéaire, la centralisation des gradients ou la moyenne des vecteurs singuliers est suffisante dans le cas de faible dimension, alors que la méthode de la puissance itérée distribuée, avec aussi peu qu'une ou deux itérations par époque, excelle dans le cas de grande dimension. La librairie Python développée pour les expériences est modulaire, extensible et prête à être déployée dans un contexte industriel. Cette étude a rempli sa fonction de preuve de concept. Suivant le chemin qu'il met en place, des solveurs peuvent être implémentés pour différentes infrastructures, parmi lesquelles des clusters GPU, pour résoudre des problèmes pratiques dans des contextes spécifiques. En outre, ses excellentes performances dans le jeu de données ImageNet le rendent prometteur pour l'apprentissage en profondeur. / Learning low-rank matrices is a problem of great importance in statistics, machine learning, computer vision, recommender systems, etc. Because of its NP-hard nature, a principled approach is to solve its tightest convex relaxation : trace norm minimization. Among various algorithms capable of solving this optimization is the Frank-Wolfe method, which is particularly suitable for high-dimensional matrices. In preparation for the usage of distributed infrastructures to further accelerate the computation, this study aims at exploring the possibility of executing the Frank-Wolfe algorithm in a star network with the Bulk Synchronous Parallel (BSP) model and investigating its efficiency both theoretically and empirically. In the theoretical aspect, this study revisits Frank-Wolfe's fundamental deterministic sublinear convergence rate and extends it to nondeterministic cases. In particular, it shows that with the linear subproblem appropriately solved, Frank-Wolfe can achieve a sublinear convergence rate both in expectation and with high probability. This contribution lays the theoretical foundation of using power iteration or Lanczos iteration to solve the linear subproblem for trace norm minimization. In the algorithmic aspect, within the BSP model, this study proposes and analyzes four strategies for the linear subproblem as well as methods for the line search. Moreover, noticing Frank-Wolfe's rank-1 update property, it updates the gradient recursively, with either a dense or a low-rank representation, instead of repeatedly recalculating it from scratch. All of these designs are generic and apply to any distributed infrastructures compatible with the BSP model. In the empirical aspect, this study tests the proposed algorithmic designs in an Apache SPARK cluster. According to the experiment results, for the linear subproblem, centralizing the gradient or averaging the singular vectors is sufficient in the low-dimensional case, whereas distributed power iteration, with as few as one or two iterations per epoch, excels in the high-dimensional case. The Python package developed for the experiments is modular, extensible and ready to deploy in an industrial context. This study has achieved its function as proof of concept. Following the path it sets up, solvers can be implemented for various infrastructures, among which GPU clusters, to solve practical problems in specific contexts. Besides, its excellent performance in the ImageNet dataset makes it promising for deep learning.

Cette thèse porte essentiellement sur l'étude d'algorithmes d'optimisation. Les problèmes de programmation intervenant en apprentissage automatique ou en traitement du signal sont dans beaucoup de cas composites, c'est-à-dire qu'ils sont contraints ou régularisés par des termes non lisses. Les méthodes proximales sont une classe d'algorithmes très efficaces pour résoudre de tels problèmes. Cependant, dans les applications modernes de sciences des données, les fonctions à minimiser se représentent souvent comme une espérance mathématique, difficile ou impossible à évaluer. C'est le cas dans les problèmes d'apprentissage en ligne, dans les problèmes mettant en jeu un grand nombre de données ou dans les problèmes de calcul distribué. Pour résoudre ceux-ci, nous étudions dans cette thèse des méthodes proximales stochastiques, qui adaptent les algorithmes proximaux aux cas de fonctions écrites comme une espérance. Les méthodes proximales stochastiques sont d'abord étudiées à pas constant, en utilisant des techniques d'approximation stochastique. Plus précisément, la méthode de l'Equation Differentielle Ordinaire est adaptée au cas d'inclusions differentielles. Afin d'établir le comportement asymptotique des algorithmes, la stabilité des suites d'itérés (vues comme des chaines de Markov) est étudiée. Ensuite, des généralisations de l'algorithme du gradient proximal stochastique à pas décroissant sont mises au point pour resoudre des problèmes composites. Toutes les grandeurs qui permettent de décrire les problèmes à résoudre s'écrivent comme une espérance. Cela inclut un algorithme primal dual pour des problèmes régularisés et linéairement contraints ainsi qu'un algorithme d'optimisation sur les grands graphes. / This thesis mainly studies optimization algorithms. Programming problems arising in signal processing and machine learning are composite in many cases, i.e they exhibit constraints and non smooth regularization terms. Proximal methods are known to be efficient to solve such problems. However, in modern applications of data sciences, functions to be minimized are often represented as statistical expectations, whose evaluation is intractable. This cover the case of online learning, big data problems and distributed computation problems. To solve this problems, we study in this thesis proximal stochastic methods, that generalize proximal algorithms to the case of cost functions written as expectations. Stochastic proximal methods are first studied with a constant step size, using stochastic approximation techniques. More precisely, the Ordinary Differential Equation method is adapted to the case of differential inclusions. In order to study the asymptotic behavior of the algorithms, the stability of the sequences of iterates (seen as Markov chains) is studied. Then, generalizations of the stochastic proximal gradient algorithm with decreasing step sizes are designed to solve composite problems. Every quantities used to define the optimization problem are written as expectations. This include a primal dual algorithm to solve regularized and linearly constrained problems and an optimization over large graphs algorithm.

Le domaine de recherche de cette thèse est l'optimisation linéaire robuste en deux étapes. Nous sommes intéressés par des algorithmes d'exploration de sa structure et aussi pour ajouter des alternatives afin d'atténuer le conservatisme inhérent à une solution robuste. Nous développons des algorithmes qui incorporent ces alternatives et sont personnalisés pour fonctionner avec des exemples de problèmes à moyenne ou grande échelle. En faisant cela, nous expérimentons une approche holistique du conservatisme en optimisation linéaire robuste et nous rassemblons les dernières avancées dans des domaines tels que l'optimisation robuste basée sur les données, optimisation robuste par distribution et optimisation robuste adaptative. Nous appliquons ces algorithmes dans des applications définies du problème de conception / chargement du réseau, problème de planification, problème combinatoire min-max-min et problème d'affectation de la flotte aérienne. Nous montrons comment les algorithmes développés améliorent les performances par rapport aux implémentations précédentes. / The research scope of this thesis is two-stage robust linear optimization. We are interested in investigating algorithms that can explore its structure and also on adding alternatives to mitigate conservatism inherent to a robust solution. We develop algorithms that incorporate these alternatives and are customized to work with rather medium or large scale instances of problems. By doing this we experiment a holistic approach to conservatism in robust linear optimization and bring together the most recent advances in areas such as data-driven robust optimization, distributionally robust optimization and adaptive robust optimization. We apply these algorithms in defined applications of the network design/loading problem, the scheduling problem, a min-max-min combinatorial problem and the airline fleet assignment problem. We show how the algorithms developed improve performance when compared to previous implementations.

De nos jours, les informations liées au déplacement et à la mobilité dans un réseau de transport représentent sans aucun doute un potentiel important.Ces travaux visent à mettre en œuvre un Système d’Information de Service d’Aide à la Mobilité Urbaine (SISAMU).Le SISAMU doit pouvoir procéder par des processus de décomposition des requêtes simultanées en un ensemble de tâches indépendantes. Chaque tâche correspond à un service qui peut être proposé par plusieurs fournisseurs d’information en concurrence, avec différents coûts, temps de réponse et formats. Le SISAMU est lié à un Réseau informatique Etendu et distribué de Transport Multimodal (RETM) qui comporte plusieurs sources d’information hétérogènes des différents services proposés aux utilisateurs de transport. L’aspect dynamique, distribué et ouvert du problème, nous a conduits à adopter une modélisation multi-agent pour assurer au système une évolution continue et une flexibilité pragmatique. Pour ce faire, nous avons proposé d’automatiser la modélisation des services en utilisant la notion d’ontologie. Notre SISAMU prend en considération les éventuelles perturbations sur le RETM.Ansi, nous avons créé un protocole de négociation entre les agents. Le protocole de négociation proposé qui utilise l’ontologie de la cartographie se base sur un système de gestion des connaissances pour soutenir l'hétérogénéité sémantique. Nous avons détaillé l’Algorithme de Reconstruction Dynamique des Chemins des Agents (ARDyCA) qui est basé sur l’approche de l’ontologie cartographique. Finalement, les résultats présentés dans cette thèse justifient l’utilisation de l’ontologie flexible et son rôle dans le processus de négociation / Nowadays, information related on displacement and mobility in a transport network represents certainly a significant potential. So, this work aims to modeling, to optimize and to implement an Information System of Services to Aid the Urban Mobility (ISSAUM).The ISSAUM has firstly to decompose each set of simultaneous requests into a set of sub-requests called tasks. Each task corresponds to a service which can be proposed different by several information providers with different. An information provider which aims to propose some services through our ISSAUM has to register its ontology. Indeed, ISSAUM is related to an Extended and distributed Transport Multimodal Network (ETMN) which contains several heterogeneous data sources. The dynamic and distributed aspects of the problem incite us to adopt a multi-agent approach to ensure a continual evolution and a pragmatic flexibility of the system. So, we proposed to automate the modeling of services by using ontology idea. Our ISSAUM takes into account possible disturbance through the ETMN. In order to satisfy user requests, we developed a negotiation protocol between our system agents. The proposed ontology mapping negotiation model based on the knowledge management system for supporting the semantic heterogeneity and it organized as follow: Negotiation Layer (NL), the Semantic Layer (SEL), and the Knowledge Management Systems Layer(KMSL).We detailed also the reassignment process by using Dynamic Reassigned Tasks (DRT) algorithm supporting by ontology mapping approach. Finally, the experimental results presented in this thesis, justify the using of the ontology solution in our system and its role in the negotiation process