Une grande partie des résultats rapportés dans cette thèse est basée sur une observation qui n'a jamais été faite pour les communications sans fil et le contrôle de puissance en particulier: les niveaux de puissance d'émission et plus généralement les matrices de covariance peuvent être exploitées pour intégrer des informations de coordination. Les échantillons de rétroaction dépendants des interférences peuvent être exploités comme canal de communication. Premièrement, nous montrons que le fameux algorithme itératif de remplissage d'eau n'exploite pas suffisamment l'information disponible en termes d'utilité-somme. En effet, nous montrons que l'information globale d'état de canal peut être acquise à partir de la seule connaissance d'une rétroaction de type SINR. Une question naturelle se pose alors. Est-il possible de concevoir un algorithme de contrôle de puissance distribué qui exploite au mieux les informations disponibles? Pour répondre à cette question, nous dérivons la caractérisation de la région d'utilité pour le problème considéré et montrons comment exploiter cette caractérisation non seulement pour mesurer globalement l'efficacité mais aussi pour obtenir des fonctions de contrôle de puissance à un coup efficaces au niveau global. Motivés par le succès de notre approche sur les réseaux d'interférences mono bande et multibande, nous nous sommes demandé si elle pourrait être exploitée pour les réseaux MIMO. Nous avons identifié au moins un scénario très pertinent. En effet, nous montrons que l'alignement d'interférence opportuniste peut être implémenté en supposant seulement une rétroaction de covariance d'interférence plus bruit à l'émetteur secondaire. Puis, dans le dernier chapitre, nous généralisons le problème de la quantification, la motivation étant donnée par certaines observations faites dans les chapitres précédents. Premièrement, nous supposons que le quantificateur et le déquantificateur sont conçus pour maximiser une fonction d'utilité générale au lieu de la fonction de distorsion classique. Deuxièmement, nous supposons que le quantificateur et le déquantificateur peuvent avoir des fonctions d'utilité différentes. Cela soulève des problèmes techniques non triviaux, notre revendication est de faire un premier pas dans la résolution d'eux. / A large part of the results reported in this thesis is based on an observation which has never been made for wireless communications and power control in particular: transmit power levels and more generally transmit covariance matrices can be exploited to embed information such as coordination information and available interference-dependent feedback samples can be exploited as a communication channel. First, we show that the famous iterative water-filling algorithm does not exploit the available information sufficiently well in terms of sum-utility. Indeed, we show that global channel state information can be acquired from the sole knowledge of an SINR-type feedback. A natural question then arises. Is it possible to design a distributed power control algorithm which exploits as well as possible the available information? To answer this question, we derive the characterization of the utility region for the considered problem and show how to exploit this characterization not only to measure globally efficiency but also to obtain globally efficient one-shot power control functions. Motivated by the success of our approach for single-band and multi-band interference networks, we asked ourselves whether it could be exploited for MIMO networks. We have identified at least one very relevant scenario. Indeed, we show that opportunistic interference alignment can be implemented by only assuming interference-plus-noise covariance feedback at the secondary transmitter. Then, in the last chapter, we generalize the problem of quantization, the motivation for this being given by some observations made in the previous chapters. First, we assume that the quantizer and de-quantizer are designed to maximize a general utility function instead of the conventional distortion function. Second, we assume that the quantizer and de-quantizer may have different utility functions. This raises non-trivial technical problems, our claim is to make a very first step into solving them.

In economical and sustainable operation of cyber-physical systems, a number of entities need to often cooperate over a communication network to solve optimization problems. A challenging aspect in the design of robust distributed solution algorithms to these optimization problems is that as technology advances and the networks grow larger, the communication bandwidth used to coordinate the solution is limited. Moreover, even though most research has focused distributed convex optimization, in cyberphysical systems nonconvex problems are often encountered, e.g., localization in wireless sensor networks and optimal power flow in smart grids, the solution of which poses major technical difficulties. Motivated by these challenges this thesis investigates distributed optimization with emphasis on limited communication for both convex and nonconvex structured problems. In particular, the thesis consists of four articles as summarized below. The first two papers investigate the convergence of distributed gradient solution methods for the resource allocation optimization problem, where gradient information is communicated at every iteration, using limited communication. In particular, the first paper investigates how distributed dual descent methods can perform demand-response in power networks by using one-way communication. To achieve the one-way communication, the power supplier first broadcasts a coordination signal to the users and then updates the coordination signal by using physical measurements related to the aggregated power usage. Since the users do not communicate back to the supplier, but instead they only take a measurable action, it is essential that the algorithm remains primal feasible at every iteration to avoid blackouts. The paper demonstrates how such blackouts can be avoided by appropriately choosing the algorithm parameters. Moreover, the convergence rate of the algorithm is investigated. The second paper builds on the work of the first paper and considers more general resource allocation problem with multiple resources. In particular, a general class of quantized gradient methods are studied where the gradient direction is approximated by a finite quantization set. Necessary and sufficient conditions on the quantization set are provided to guarantee the ability of these methods to solve a large class of dual problems. A lower bound on the cardinality of the quantization set is provided, along with specific examples of minimal quantizations. Furthermore, convergence rate results are established that connect the fineness of the quantization and number of iterations needed to reach a predefined solution accuracy. The results provide a bound on the number of bits needed to achieve the desired accuracy of the optimal solution. The third paper investigates a particular nonconvex resource allocation problem, the Optimal Power Flow (OPF) problem, which is of central importance in the operation of power networks. An efficient novel method to address the general nonconvex OPF problem is investigated, which is based on the Alternating Direction Method of Multipliers (ADMM) combined with sequential convex approximations. The global OPF problem is decomposed into smaller problems associated to each bus of the network, the solutions of which are coordinated via a light communication protocol. Therefore, the proposed method is highly scalable. The convergence properties of the proposed algorithm are mathematically and numerically substantiated. The fourth paper builds on the third paper and investigates the convergence of distributed algorithms as in the third paper but for more general nonconvex optimization problems. In particular, two distributed solution methods, including ADMM, that combine the fast convergence properties of augmented Lagrangian-based methods with the separability properties of alternating optimization are investigated. The convergence properties of these methods are investigated and sufficient conditions under which the algorithms asymptotically reache the first order necessary conditions for optimality are established. Finally, the results are numerically illustrated on a nonconvex localization problem in wireless sensor networks. The results of this thesis advocate the promising convergence behaviour of some distributed optimization algorithms on nonconvex problems. Moreover, the results demonstrate the potential of solving convex distributed resource allocation problems using very limited communication bandwidth. Future work will consider how even more general convex and nonconvex problems can be solved using limited communication bandwidth and also study lower bounds on the bandwidth needed to solve general resource allocation optimization problems. / <p>QC 20160203</p>

Cette thèse porte sur la construction des algorithmes distribués pour l’optimisation de la production et du partage de ressources au sein d’un réseau de large dimension. Notamment, on se concentre sur les réseaux électriques et les réseaux cellulaires 5G. On considère dans le cas des réseaux électriques le problème OPF (Optimal Power Flow) dans lequel on vise à faire la gestion et l’optimisation de la production de l’énergie électrique d’une manière distribuée. On se concentre sur une version linéarisée du problème, la DC-OPF (Direct-Current Optimal Power Flow). Comme le problème d’optimisation est convexe dans ce cas, on vise à minimiser le coût de production de l’énergie tout en respectant les limites des lignes de transmission et les contraintes caractéristiques du système. Dans le cas des réseaux cellulaires, on formule un problème de Caching. On a pour but de réduire l’utilisation du backhaul liant les stations de base et le contrôleur du réseau. Les stations de base sont équipées d’une capacité de stockage limitée. Ils visent à trouver d’une manière optimale les fichiers à stocker dans le but de réduire une certaine fonction de coût sur l’utilisation du backhaul et sur le partage des fichiers avec les autres stations de base. L’approche adoptée dans cette thèse consiste à appliquer l’ADMM (Alternating Direction Method of Multipliers), une méthode d’optimisation de manière itérative, à un problème d’optimisation que l’on a préalablement reformulée de façon adéquate. Ce problème permet à la fois de décrire le DC-OPF et le problème de Caching. On démontre la convergence de cette méthode quand elle est appliquée noeud par noeudd’une manière totalement distribuée. Ainsi que dans le cas où le réseau est divisé en plusieurs zones. Ces zones peuvent se chevaucher mais aussi elles peuvent être séparées ou indépendantes. De plus, dans le contexte d’un réseau à zones, on démontre que l’application de l’ADMM d’une manière aléatoire par une seule zone converge aussi vers la solution optimale du problème. / This thesis focuses on the construction of distributed algorithms for optimizing resource production in a large interconnected system. In particular, it focuses on power grid and 5G cellular networks. In the case of power grid networks, we consider the OPF (Optimal Power Flow) problem in which one seeks to manage and optimize the production of electrical energy in a distributed manner. We focus on a linearized version of the problem, the DC-OPF (Direct- Current Optimal Power Flow) problem. This optimization problem is convex; the aim is to minimize the cost of energy generation while respecting the limits of the transmission line and the power flow constraints. In the case of 5G cellular networks, we formulate a caching problem. We aim to offload the backhaul link usage connecting the small bases stations (SBSs) to the central scheduler (CS). The SBSs are equipped with a limited storage capacity. We seek to find the optimal way to store files so as to reduce the cost on the use of backhaul and sharing files with other SBSs. The approach adopted in this thesis is to apply the ADMM (Alternating Direction Method of Multipliers), an optimization method that is applied iteratively, to an optimization problem that we adequately formulated previously. This problem can both describe the DC-OPF problem and the Caching problem. We prove the convergence of the method when applied node by node in a fully distributed manner. Additionally, we prove its convergence in the case where the network is divided into multiple areas or nations that may or may not overlap. Furthermore, in the context of a network with multiple areas, we show that the application of ADMM in a random manner by a single randomly chosen area also converges to the optimal solution of the problem.

La généralisation concomitante de consommateurs d'électricité flexibles et de producteurs imparfaitement contrôlables invite à utiliser les complémentarités de ces acteurs afin d'améliorer leur intégration dans les systèmes d'énergie. Dans le cadre de ces travaux de doctorat, la collaboration entre une flotte de véhicules électriques et une centrale photovoltaïque est étudiée. Un problème générique est tout d'abord défini afin d'augmenter la prévisibilité des échanges entre un réseau électrique et le système collaboratif ainsi créé qui devra respecter un profil d'engagement de puissance échangée. La gestion de ce système est traduite en un problème d'optimisation dans lequel on cherche à compenser les erreurs de prévision de la production photovoltaïque à l'aide de la flexibilité des recharges. Ce problème est multi-temporel du fait de la présence de batteries, stochastique à cause de la disponibilité des véhicules et des erreurs de prévision, et enfin de grande dimension puisqu'à l'échelle d'une flotte entière.Pour le résoudre, la modélisation du comportement et du vieillissement des batteries Li-ion est discutée afin d'établir des compromis entre justesse du modèle, impact sur la décision finale et coût de calcul. Par ailleurs, un modèle de Markov caché original est spécifiquement développé afin de capturer les structures temporelles de l'erreur de prévision de production photovoltaïque. Cette étude est fondée sur des données réelles de production d'une centrale et des données de prévision correspondantes.Le problème de recharge optimale d'une flotte de véhicules agrégée en une batterie équivalente est résolu par la méthode de la programmation dynamique stochastique. La sensibilité des lois de gestion obtenues est discutée vis à vis des modèles utilisés pour décrire l'erreur de prévision ou le comportement des batteries. Le vieillissement des batteries est traduit par plusieurs modèles, dont on examine les conséquences sur le dimensionnement optimal de la flotte de véhicules par rapport à la puissance crête de la centrale photovoltaïque.Enfin la puissance de recharge optimale pour chacun des véhicules de la flotte est déduite à l'aide d'un problème de partage qui est résolu par optimisation distribuée --- Alternating Direction Method of Multipliers --- et programmation dynamique. Une attention particulière est prêtée à la manière dont les préférences individuelles de chaque utilisateur peuvent être prises en compte au sein d'une flotte. Le cas d'une limitation des échanges d'information possibles entre les véhicules est investigué. Le dimensionnement optimal entre une flotte et une centrale photovoltaïque est finalement analysé pour plusieurs modèles économiques envisageables. L'interaction entre dimensionnement et gestion est traitée à l'aide d'une co-optimisation. / Simultaneous development of flexible electricity consumers and of intermittent renewable producers calls for using their complementarities. It could foster their overall integration in power systems. For the purpose of this doctoral thesis, the collaboration between an electric vehicle fleet and a photovoltaic plant is studied. First of all, a generic problem is set up to improve the predictability of the power exchange between the power grid and the so called collaboratif system. It should therefore fulfill a commitment profile constraint. The intraday management of this system consists in an optimisation problem which objective is to mitigate the production forecast errors by charging power flexibility. This is a multitime step problem, because of the battery intertia. The random availibility of vehicles and the forecast errors also make it stochastic. Finally there is a huge number of variables as it is spread other an entiere fleet.Upstream of the problem resolution, the modeling of the dynamic behaviour and of the aging of Lithium Ion batteries is discussed. It results in a range of compromises between precision, impact on the final decision and computational cost. Furthermore, a hidden Markov model is proposed and developped so as to handle temporal structures of the forecast error of the photovoltaic production. This analysis is based on production data of a real plant and on associated forecasts.An electric vehicle fleet is considered as an equivalent agregated battery. Its optimal charging power is sorted out using stochastic dynamic programming. The sensitivity of the resulting management strategies is assessed against the models which describe the production forecast error or battery behaviour. The battery aging is rendered by several models which we discuss the consequences over the optimal sizing of an electric vehicle fleet regarding to the plant power.Then the optimal charing power for each one of the vehicles among a fleet is deduced using a sharing problem. The resolution is carried out using distributed optimisation --- Alternating Direction Method of Multipliers --- and dynamic programming. A specific attention is devoted to the individual mobility priorities of the vehicles users. The vehicle charging power is thus differenticiated according to each one preferences. We also investigate a situation where information exchanges are limited. The optimal sizing of an electric vehicle fleet associated with a photovoltaic plant is finaly considered under several possibilities of economic model. The coupling between sizing and daily management is tackled thanks to a co-optimization.

Optimization problems are ubiquitous in all quantitative scientific disciplines, from computer science and engineering to operations research and economics. Developing algorithms for solving various optimization problems has been the focus of mathematical research for years. In the last decade, optimization research has become even more popular due to its applications in the rapidly developing field of machine learning. In this thesis, we discuss a few fundamental and well-studied optimization problem classes: decentralized distributed optimization (Chapters 2 to 4), distributed optimization under similarity (Chapter 5), affinely constrained optimization (Chapter 6), minimax optimization (Chapter 7), and high-order optimization (Chapter 8). For each problem class, we develop the first provably optimal algorithm: the complexity of such an algorithm cannot be improved for the problem class given. The proposed algorithms show state-of-the-art performance in practical applications, which makes them highly attractive for potential generalizations and extensions in the future.

The emerging technology of Cyberphysical systems consists of networked computing, sensing, and actuator devices used to monitor, connect, and control physical phenomena. In order to economically and sustainably operate Cyberphysical systems, their devices need to cooperate over a communication network to solve optimization problems. For example, in smart power grids, smart meters cooperatively optimize the grid performance, and in wireless sensor networks a number of sensors cooperate to find optimal estimators of real-world parameters. A challenging aspect in the design of distributed solution algorithms to these optimization problems is that while the technology advances and the networks grow larger, the communication bandwidth available to coordinate the solution remains limited. Motivated by this challenge, this thesis investigates the convergence of distributed solution methods for resource allocation optimization problems, where gradient information is communicated at every iteration, using limited communication. This problem is approached from three different perspectives, each presented in a separate paper.  The investigation of the three papers demonstrate promises and limits of solving distributed resource allocation problems using limited communication bandwidth. Future work will consider how even more general problems can be solved using limited communication bandwidth and also study different communication constraints. / <p>QC 20170424</p>

Cette thèse étudie des problèmes d’optimisation distribuée avec différentes structures d’observationset leurs applications aux réseaux sans fil et aux problèmes de Smart Grids. Spécifiquement,une structure d’observation asymétrique entre deux agents est considérée, où un premieragent a connaissance complète à propos de la réalisation d’un état aléatoire, et l’autre agent neconnaît rien à propos de cet état. Dans ce contexte, la question est de savoir comment transmettrede l’information depuis le premier agent vers le second agent dans le but d’utiliser de manièreoptimale les ressources de communication. Plusieurs modèles sont étudiés dans cette thèse. Pourtous, un élément commun est le fait que la source d’information doit être encodée de manièreappropriée pour optimiser l’utilisation de la configuration du système. Un premier modèle estétudié où aucun canal de communication n’est disponible entre les agents et ils ont une fonctiond’utilité commune. Cependant, le seul moyen de communiquer est via les actions choisiespar les agents. Comme les actions ont une influence sur le paiement, l’agent informé encode saconnaissance à propos de l’état dans ses actions, qui seront observées de manière imparfaite parle second agent. Ce dernier décodera l’information et choisira ses actions dans le but de maximiserla fonction objectif commune. Nous utilisons des outils de théorie de l’information pourcaractériser ce compromis optimal par une contrainte d’information, et appliquons ce scénario àun problème de contrôle de puissance pour un canal à interférence. Notre nouvelle stratégie (lecontrôle de puissance codé) donne des gains très prometteurs comparés aux approches classiques.Dans une seconde partie, nous considérons qu’il existe un canal dédié de communication, c’està-dire que les actions de l’agent informé n’ont pas d’influence sur le paiement et sont seulementutiles pour la transmission d’information. De plus, les agents sont supposés avoir des intérêtsdivergents, si bien que l’agent informé n’a pas nécessairement d’incitation à envoyer tout sonsavoir à l’agent non informé. La théorie des jeux et les jeux de « Cheap talk » en particulier sontle bon cadre pour analyser ce genre de problème. Nous caractérisons le schéma de signal sur lequelles agents se seront mis d’accord. Ce schéma amènera à un équilibre de Nash, est donc optimiserala façon dont la communication est faite. Ce modèle est d’un intérêt particulier pour les réseauxde véhicules électriques où un véhicule électrique doit envoyer son besoin en terme de puissancede charge à un aggrégateur qui choisira un niveau de charge effectif pour le véhicule électrique.Ce dernier ne se souciera que de son besoin, alors que l’aggrégateur se soucie également de l’étatdu réseau. Ce modèle aide à optimiser la façon dont le réseau est utilisé.Enfin, nous considérons un modèle avec plus de deux agents, où le but principal est pourtous les agents de retrouver l’observation parfaite des actions passées de tous les agents. Ceci estd’un intérêt très particulier d’un point de vue de la théorie des jeux pour caractériser les utilitésespérées de long terme des agents. Dans ce modèle, nous ajoutons un encodeur qui observeparfaitement toutes les actions passées et aidera les agents à obtenir l’observation parfaite. Enfait, ceci sera possible si la bonne contrainte d’information est satisfaite. Nous caractérisonsdonc cette dernière, en utilisant un schéma de codage hybride combinant des outils classiques dethéorie de l’information ainsi que des outils de la théorie des graphes / This thesis studies distributed optimization problems with different observation structuresand application to wireless network and Smart Grids problems. Specifically, an asymmetricobservation structure between two agents is considered, where a first agent has full knowledgeabout the realization of a random state, and the other agent does not know anything about thisstate. In this context, the question is how to transmit information from the first agent to thesecond agent in order to use in an optimal way the communication resources. Several modelsare studied in this thesis. For all of them, a common element is that the information source hasto be encoded in an appropriate manner to optimize the use of the system’s configuration. Afirst model is studied where no dedicated channel for communication is available between agentsand they have the same objective function. Therefore, the only way communication is possible isthrough the actions chosen by agents. As actions are payoff relevant, the first agent has to findthe optimal tradeoff between transmission of information and payoff maximization. The informedagent encodes his knowledge about the state into his actions, which will be imperfectly observedby the second agent. The latter will decode the information and choose his actions in order tomaximize the common objective function. We use tools from information theory to characterizethis optimal tradeoff by an information constraint, and apply this scenario to a power controlproblem in an interference channel setting. Our new strategy (the coded power control ) givessome promising gains compare to classical approaches.In a second part, we consider that there exists a dedicated channel for communication, that isto say the actions of the informed agent are not payoff relevant and are only useful for transmissionof information. Furthermore, agents are supposed to have diverging interests, so that the informedagent does not necessarily have an incentive to send all his knowledge to the uninformed agent.Game theory and Cheap talk game in particular appears to be the right framework to analyzethis problem. We characterize the signal scheme that agents will agree on. This scheme willlead to a Nash Equilibrium, thus will optimize the way communication is done. This model is ofparticular interest for electrical vehicles networks where an electrical vehicle has to send his needin term of power to an aggregator which will choose an effective charging level for the electricalvehicle. The latter only cares about his need in term of power whereas the aggregator also takesinto account the network status. The considered model help to optimize the way the network isused.We finally consider a model with more than two agents, where the main goal is for all agentsto retrieve perfect observations of all past actions of all agents. This is of particular interest ina game theory point of view to characterize the long term expected utilities of the agents. Inthis model, we add an encoder who perfectly oberves all past actions and will help agents tohave perfect monitoring. In fact, this is possible if the right information constraint is satisfied.We thus characterized the latter, using a hybrid coding scheme combining classical informationtheoretic scheme and tools from graph theory.

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.

Network utility maximization has emerged as a powerful tool in studying flow control, resource allocation and other cross-layer optimization problems. In this work, we study a flow control problem in the optimization framework. The objective is to maximize the sum utility of the users subject to the flow constraints of the network. The utility maximization is solved in a distributed setting; the network operator does not know the user utility functions and the users know neither the rate choices of other users nor the flow constraints of the network. We build upon a popular decomposition technique proposed by Kelly [Eur. Trans. Telecommun., 8(1), 1997] to solve the utility maximization problem in the aforementioned distributed setting. The technique decomposes the utility maximization problem into a user problem, solved by each user and a network problem solved by the network. We propose an iterative algorithm based on this decomposition technique. In each iteration, the users communicate to the network their willingness to pay for the network resources. The network allocates rates in a proportionally fair manner based on the prices communicated by the users. The new feature of the proposed algorithm is that the rates allocated by the network remains feasible at all times. We show that the iterates put out by the algorithm asymptotically tracks a differential inclusion. We also show that the solution to the differential inclusion converges to the system optimal point via Lyapunov theory. We use a popular benchmark algorithm due to Kelly et al. [J. of the Oper. Res. Soc., 49(3), 1998] that involves fast user updates coupled with slow network updates in the form of additive increase and multiplicative decrease of the user flows. The proposed algorithm may be viewed as one with fast user update and fast network update that keeps the iterates feasible at all times. Simulations suggest that our proposed algorithm converges faster than the aforementioned benchmark algorithm. When the flows originate or terminate at a single node, the network problem is the maximization of a so-called d-separable objective function over the bases of a polymatroid. The solution is the lexicographically optimal base of the polymatroid. We map the problem of finding the lexicographically optimal base of a polymatroid to the geometrical problem of finding the concave cover of a set of points on a two-dimensional plane. We also describe an algorithm that finds the concave cover in linear time. Next, we consider the minimization of a more general objective function, i.e., a separable convex function, over the bases of a polymatroid with a special structure. We propose a novel decomposition algorithm and show the proof of correctness and optimality of the algorithm via the theory of polymatroids. Further, motivated by the need to handle piece-wise linear concave utility functions, we extend the decomposition algorithm to handle the case when the separable convex functions are not continuously differentiable or not strictly convex. We then provide a proof of its correctness and optimality.