An increased penetration of renewable energy into the electric power grid is desirable from an environmental standpoint as well as an economical one. However, renewable sources such as wind and solar energy are often variable and intermittent, and additionally, are non-dispatchable. Also, the locations with the highest amount of available wind or solar may be located in areas that are far from areas with high levels of demand, and these areas may be under the control of separate, individual entities. In this dissertation, a method that coordinates these areas, accounts for the variability and intermittency, reduces the impact of renewable energy forecast errors, and increases the overall social benefit in the system is developed. The approach for the purpose of integrating intermittent energy sources into the electric power grid is considered from both the planning and operations stages. In the planning stage, two-stage stochastic optimization is employed to find the optimal size and location for a storage device in a transmission system with the goal of reducing generation costs, increasing the penetration of wind energy, alleviating line congestions, and decreasing the impact of errors in wind forecasts. The size of this problem grows dramatically with respect to the number of variables and constraints considered. Thus, a scenario reduction approach is developed which makes this stochastic problem computationally feasible. This scenario reduction technique is derived from observations about the relationship between the variance of locational marginal prices corresponding to the power balance equations and the optimal storage size. Additionally, a probabilistic, or chance, constrained model predictive control (MPC) problem is formulated to take into account wind forecast errors in the optimal storage sizing problem. A probability distribution of wind forecast errors is formed and incorporated into the original storage sizing problem. An analytical form of this constraint is derived to directly solve the optimization problem without having to use Monte-Carlo simulations or other techniques that sample the probability distribution of forecast errors. In the operations stage, a MPC AC Optimal Power Flow problem is decomposed with respect to physical control areas. Each area performs an independent optimization and variable values on the border buses between areas are exchanged at each Newton-Raphson iteration. Two modifications to the Approximate Newton Directions (AND) method are presented and used to solve the distributed MPC optimization problem, both with the intention of improving the original AND method by improving upon the convergence rate. Methods are developed to account for numerical difficulties encountered by these formula- tions, specifically with regards to Jacobian singularities introduced due to the intertemporal constraints. Simulation results show convergence of the decomposed optimization problem to the centralized result, demonstrating the benefits of coordinating control areas in the IEEE 57- bus test system. The benefit of energy storage in MPC formulations is also demonstrated in the simulations, reducing the impact of the fluctuations in the power supply introduced by intermittent sources by coordinating resources across control areas. An overall reduction of generation costs and increase in renewable penetration in the system is observed, with promising results to effectively and efficiently integrate renewable resources into the electric power grid on a large scale.

<p>Distributed optimization methods allow us to decompose an optimization problem</p><p>into smaller, more manageable subproblems that are solved in parallel. For this</p><p>reason, they are widely used to solve large-scale problems arising in areas as diverse</p><p>as wireless communications, optimal control, machine learning, artificial intelligence,</p><p>computational biology, finance and statistics, to name a few. Moreover, distributed</p><p>algorithms avoid the cost and fragility associated with centralized coordination, and</p><p>provide better privacy for the autonomous decision makers. These are desirable</p><p>properties, especially in applications involving networked robotics, communication</p><p>or sensor networks, and power distribution systems.</p><p>In this thesis we propose the Accelerated Distributed Augmented Lagrangians</p><p>(ADAL) algorithm, a novel decomposition method for convex optimization prob-</p><p>lems with certain separability structure. The method is based on the augmented</p><p>Lagrangian framework and addresses problems that involve multiple agents optimiz-</p><p>ing a separable convex objective function subject to convex local constraints and</p><p>linear coupling constraints. We establish the convergence of ADAL and also show</p><p>that it has a worst-case O(1/k) convergence rate, where k denotes the number of</p><p>iterations.</p><p>Moreover, we show that ADAL converges to a local minimum of the problem</p><p>for cases with non-convex objective functions. This is the first published work that</p><p>formally establishes the convergence of a distributed augmented Lagrangian method</p><p>ivfor non-convex optimization problems. An alternative way to select the stepsizes</p><p>used in the algorithm is also discussed. These two contributions are independent</p><p>from each other, meaning that convergence of the non-convex ADAL method can</p><p>still be shown using the stepsizes from the convex case, and, similarly, convergence</p><p>of the convex ADAL method can be shown using the stepsizes proposed in the non-</p><p>convex proof.</p><p>Furthermore, we consider cases where the distributed algorithm needs to operate</p><p>in the presence of uncertainty and noise and show that the generated sequences of</p><p>primal and dual variables converge to their respective optimal sets almost surely. In</p><p>particular, we are concerned with scenarios where: i) the local computation steps</p><p>are inexact or are performed in the presence of uncertainty, and ii) the message</p><p>exchanges between agents are corrupted by noise. In this case, the proposed scheme</p><p>can be classified as a distributed stochastic approximation method. Compared to</p><p>existing literature in this area, our work is the first that utilizes the augmented</p><p>Lagrangian framework. Moreover, the method allows us to solve a richer class of</p><p>problems as compared to existing methods on distributed stochastic approximation</p><p>that consider only consensus constraints.</p><p>Extensive numerical experiments have been carried out in an effort to validate</p><p>the novelty and effectiveness of the proposed method in all the areas of the afore-</p><p>mentioned theoretical contributions. We examine problems in convex, non-convex,</p><p>and stochastic settings where uncertainties and noise affect the execution of the al-</p><p>gorithm. For the convex cases, we present applications of ADAL to certain popular</p><p>network optimization problems, as well as to a two-stage stochastic optimization</p><p>problem. The simulation results suggest that the proposed method outperforms</p><p>the state-of-the-art distributed augmented Lagrangian methods that are known in</p><p>the literature. For the non-convex cases, we perform simulations on certain simple</p><p>non-convex problems to establish that ADAL indeed converges to non-trivial local</p><p>vsolutions of the problems; in comparison, the straightforward implementation of the</p><p>other distributed augmented Lagrangian methods on the same problems does not</p><p>lead to convergence. For the stochastic setting, we present simulation results of</p><p>ADAL applied on network optimization problems and examine the effect that noise</p><p>and uncertainties have in the convergence behavior of the method.</p><p>As an extended and more involved application, we also consider the problem</p><p>of relay cooperative beamforming in wireless communications systems. Specifically,</p><p>we study the scenario of a multi-cluster network, in which each cluster contains</p><p>multiple single-antenna source destination pairs that communicate simultaneously</p><p>over the same channel. The communications are supported by cooperating amplify-</p><p>and-forward relays, which perform beamforming. Since the emerging problem is non-</p><p>convex, we propose an approximate convex reformulation. Based on ADAL, we also</p><p>discuss two different ways to obtain a distributed solution that allows for autonomous</p><p>computation of the optimal beamforming decisions by each cluster, while taking into</p><p>account intra- and inter-cluster interference effects.</p><p>Our goal in this thesis is to advance the state-of-the-art in distributed optimization by proposing methods that combine fast convergence, wide applicability, ease</p><p>of implementation, low computational complexity, and are robust with respect to</p><p>delays, uncertainty in the problem parameters, noise corruption in the message ex-</p><p>changes, and inexact computations.</p> / Dissertation

Cette dissertation fait face au problème de la localisation de sources, un sujet qui a été largement étudié dans la littérature récente au vu de son grand nombre d'applications. En particulier, ce travail se concentre sur le pilotage de multiples capteurs, capables de prendre des mesures ponctuelles de la quantité émise, vers la source sans faire usage d'aucune information de position, qui se trouve être indisponible dans de nombreux cas pratiques (par exemple, sous l'eau ou dans l'exploration souterraine). En faisant quelques hypothèses sur le processus de diffusion, nous développons un modèle qui permet d'utiliser des outils mathématiques (l'intégrale de Poisson et ses dérivées) pour obtenir une simple approximation du gradient de la fonction décrivant le processus de diffusion, dont la source représente le maximum, ce qui permet d'utiliser l'algorithme du gradient et trouver l'emplacement de la source. Les contributions sont de trois ordres : d'abord, nous utilisons ces outils pour résoudre le problème de la recherche d'une source en deux dimensions à travers d'un contrôle centralisé, où un seul véhicule, équipé de multiples capteurs et sans information de position, se déplace dans un environnement planaire où se trouve une source. Ensuite, nous étendons cette recherche à un cadre en trois dimensions, en considérant un engin volant équipé de capteurs qui se déplace dans l'espace ; pour ce cas plus général, outre la validation par simulations, nous fournissons également une étude théorique des propriétes de convergence de la loi de commande proposée. Enfin, nous abordons le problème de la localisation de source de façon distribuée, compte tenu de plusieurs capteurs autonomes mobiles (en deux dimensions) ; outre le problème de mettre en oeuvre l'algorithme de localisation de source de manière distribuée, nous devons garantir un contrôle de la formation approprié pour assurer l'exactitude de l'estimation du gradient, et donc atteindre la source.} / The dissertation faces the problem of source localisation, a topic which has been extensively studied in recent literature due to its large number of applications. In particular, it focuses on steering multiple sensors, able to take point-wise measurements of the emitted quantity, towards the source without making use of any position information, which happens to be unavailable in many practical cases (for example, underwater or underground exploration). By making some assumptions on the diffusion process, we develop a model which allows us to use some mathematical tools (the Poisson integral and its derivatives) for a simple approximation of the gradient of the function describing the diffusion process, whose source represents its maximum, making it possible to perform a gradient ascent to find the source location. The contributions are threefold: first, we use such tools to solve a 2-dimensional centralised source-seeking problem, where a single vehicle, equipped with multiple sensors and without position information, is moving in a planar environment where a source is supposed to emit. Then, we extend it to a 3-dimensional framework, considering a flying vehicle equipped with sensors moving in the space; for this more general case, in addition to simulation validation, we provide a theoretical study of the convergence properties of the proposed control law. Finally, we tackle the distributed source-localisation problem, considering several autonomous moving sensors (in two dimensions); in addition to the problem of implementing the source-localisation algorithm in a distributed manner, in this latter case we have also to guarantee a suitable formation control, to ensure the correctness of the gradient estimation and hence reach the source.

A fundamental assumption behind most machine learning (ML) algorithms and analyses is the sequential execution. That is, any update to the ML model can be immediately applied and the new model is always available for the next algorithmic step. This basic assumption, however, can be costly to realize, when the computation is carried out across multiple machines, linked by commodity networks that are usually 104 times slower than the memory speed due to fundamental hardware limitations. As a result, concurrent ML computation in the distributed settings often needs to handle delayed updates and perform learning in the presence of staleness. This thesis characterizes learning with staleness from three directions: (1) We extend the theoretical analyses of a number of classical ML algorithms, including stochastic gradient descent, proximal gradient descent on non-convex problems, and Frank-Wolfe algorithms, to explicitly incorporate staleness into their convergence characterizations. (2)We conduct simulation and large-scale distributed experiments to study the empirical effects of staleness on ML algorithms under indeterministic executions. Our results reveal that staleness is a key parameter governing the convergence speed for all considered ML algorithms, with varied ramifications. (3) We design staleness-minimizing parameter server systems by optimizing synchronization methods to effectively reduce the runtime staleness. The proposed optimization of a bounded consistency model utilizes the additional network bandwidths to communicate updates eagerly, relieving users of the burden to tune the staleness level. By minimizing staleness at the framework level, our system stabilizes diverging optimization paths and substantially accelerates convergence across ML algorithms without any modification to the ML programs.

Modern machine learning systems pose several new statistical, scalability, privacy and ethical challenges. With the advent of massive datasets and increasingly complex tasks, scalability has especially become a critical issue in these systems. In this thesis, we focus on fundamental challenges related to scalability, such as computational and communication efficiency, in modern machine learning applications. The underlying central message of this thesis is that classical statistical thinking leads to highly effective optimization methods for modern big data applications. The first part of the thesis investigates optimization methods for solving large-scale nonconvex Empirical Risk Minimization (ERM) problems. Such problems have surged into prominence, notably through deep learning, and have led to exciting progress. However, our understanding of optimization methods suitable for these problems is still very limited. We develop and analyze a new line of optimization methods for nonconvex ERM problems, based on the principle of variance reduction. We show that our methods exhibit fast convergence to stationary points and improve the state-of-the-art in several nonconvex ERM settings, including nonsmooth and constrained ERM. Using similar principles, we also develop novel optimization methods that provably converge to second-order stationary points. Finally, we show that the key principles behind our methods can be generalized to overcome challenges in other important problems such as Bayesian inference. The second part of the thesis studies two critical aspects of modern distributed machine learning systems — asynchronicity and communication efficiency of optimization methods. We study various asynchronous stochastic algorithms with fast convergence for convex ERM problems and show that these methods achieve near-linear speedups in sparse settings common to machine learning. Another key factor governing the overall performance of a distributed system is its communication efficiency. Traditional optimization algorithms used in machine learning are often ill-suited for distributed environments with high communication cost. To address this issue, we dis- cuss two different paradigms to achieve communication efficiency of algorithms in distributed environments and explore new algorithms with better communication complexity.

To integrate large volumes of renewables and use electricity more efficiently, many industrial trials are on-going around the world that aim to realize decentralized or hierarchical control of renewable and distributed energy resources, flexible loads and monitoring devices. As the cost and complexity involved in the centralized communications and control infrastructure may be prohibitive in controlling millions of these distributed energy resources and devices, distributed optimization methods are expected to become much more prevalent in the operation of future electric power systems, as they have the potential to address this challenge and can be applied to various applications such as optimal power ow, state estimation, voltage control, and many others. While many distributed optimization algorithms are developed mathematically, little effort has been reported so far on how these methods should actually be implemented in real-world large-scale systems. The challenges associated with this include identifying how to decompose the overall optimization problem, what communication infrastructures can support the information exchange among subproblems, and whether to coordinate the updates of the subproblems in a synchronous or asynchronous manner. This research is dedicated to developing mathematical tools to address these issues, particularly for solving the non-convex optimal power flow problem. As the first part of this thesis, we develop a partitioning method that defines the boundaries of regions when applying distributed algorithms to a power system. This partitioning method quantifies the computational couplings among the buses and groups the buses with large couplings into one region. Through numerical experiments, we show that the developed spectral partitioning approach is the key to achieving fast convergence of distributed optimization algorithms on large-scale systems. After the partitioning of the system is defined, one needs to determine whether the communications among neighboring regions are supported. Therefore, as the second part of this thesis, we propose models for centralized and distributed communications infrastructures and study the impact of communication delays on the efficiency of distributed optimization algorithms through network simulations. Our findings suggest that the centralized communications infrastructure can be prohibitive for distributed optimization and cost-effective migration paths to a more distributed communications infrastructure are necessary. As the sizes and complexities of subproblems and communication delays are generally heterogeneous, synchronous distributed algorithms can be inefficient as they require waiting for the slowest region in the system. Hence, as the third part of this thesis, we develop an asynchronous distributed optimization method and show its convergence for the considered optimal power flow problem. We further study the impact of parameter tuning, system partitioning and communication delays on the proposed asynchronous method and compare its practical performance with its synchronous counterpart. Simulation results indicate that the asynchronous approach can be more efficient with proper partitioning and parameter settings on large-scale systems. The outcome of this research provides important insights into how existing hardware and software solutions for Energy Management Systems in the power grid can be used or need to be extended for deploying distributed optimization methods, which establishes the interconnection between theoretical studies of distributed algorithms and their practical implementation. As the evolution towards a more distributed control architecture is already taking place in many utility networks, the approaches proposed in this thesis provide important tools and a methodology for adopting distributed optimization in power systems.

Decentralized multi-agent optimization has emerged as a powerful paradigm that finds broad applications in engineering design including federated machine learning and control of networked systems. In these setups, a group of agents are connected via a network with general topology. Under the communication constraint, they aim to solving a global optimization problem that is characterized collectively by their individual interests. Of particular importance are the computation and communication efficiency of decentralized optimization algorithms. Due to the heterogeneity of local objective functions, fostering cooperation across the agents over a possibly time-varying network is challenging yet necessary to achieve fast convergence to the global optimum. Furthermore, real-world communication networks are subject to congestion and bandwidth limit. To relieve the difficulty, it is highly desirable to design communication-efficient algorithms that proactively reduce the utilization of network resources. This dissertation tackles four concrete settings in decentralized optimization, and develops four provably efficient algorithms for solving them, respectively. Chapter 1 presents an overview of decentralized optimization, where some preliminaries, problem settings, and the state-of-the-art algorithms are introduced. Chapter 2 introduces the notation and reviews some key concepts that are useful throughout this dissertation. In Chapter 3, we investigate the non-smooth cost-coupled decentralized optimization and a special instance, that is, the dual form of constraint-coupled decentralized optimization. We develop a decentralized subgradient method with double averaging that guarantees the last iterate convergence, which is crucial to solving decentralized dual Lagrangian problems with convergence rate guarantee. Chapter 4 studies the composite cost-coupled decentralized optimization in stochastic networks, for which existing algorithms do not guarantee linear convergence. We propose a new decentralized dual averaging (DDA) algorithm to solve this problem. Under a rather mild condition on stochastic networks, we show that the proposed DDA attains an $\mathcal{O}(1/t)$ rate of convergence in the general case and a global linear rate of convergence if each local objective function is strongly convex. Chapter 5 tackles the smooth cost-coupled decentralized constrained optimization problem. We leverage the extrapolation technique and the average consensus protocol to develop an accelerated DDA algorithm. The rate of convergence is proved to be $\mathcal{O}\left( \frac{1}{t^2}+ \frac{1}{t(1-\beta)^2} \right)$, where $\beta$ denotes the second largest singular value of the mixing matrix. To proactively reduce the utilization of network resources, a communication-efficient decentralized primal-dual algorithm is developed based on the event-triggered broadcasting strategy in Chapter 6. In this algorithm, each agent locally determines whether to generate network transmissions by comparing a pre-defined threshold with the deviation between the iterates at present and lastly broadcast. Provided that the threshold sequence is summable over time, we prove an $\mathcal{O}(1/t)$ rate of convergence for convex composite objectives. For strongly convex and smooth problems, linear convergence is guaranteed if the threshold sequence is diminishing geometrically. Finally, Chapter 7 provides some concluding remarks and research directions for future study. / Graduate

<div>In the era of big data, the sheer volume and widespread spatial distribution of information has been promoting extensive research on distributed optimization over networks. Each computing unit has access only to a relatively small portion of the entire data and can only communicate with a relatively small number of neighbors. The goal of the system is to reach consensus on the optimal parametric model with respect to the entire data among all computing units. Existing work has provided various decentralized optimization algorithms for the purpose. However, some important questions remain unclear: (I) what is the intrinsic connection among different existing algorithms? (II) what is the min-max lower complexity bound for decentralized algorithms? Can one design an optimal decentralized algorithm in the sense that it achieves the lower complexity bound? and (III) in the presence of asynchrony and imperfect communications, can one design linearly convergent decentralized algorithms?</div><div><br></div><div> This thesis aims at addressing the above questions. (I) Abstracting from ad-hoc, specific solution methods, we propose a unified distributed algorithmic framework and analysis for a general class of optimization problems over networks. Our method encapsulates several existing first-order distributed algorithms. Distinguishing features of our scheme are: (a) When each of the agent’s functions is strongly convex, the algorithm converges at a linear rate, whose dependence on the agents’ functions and network topology is decoupled; (b) When the objective function is convex, but not strongly convex, similar decoupling as in (a) is established for the coefficient of the proved sublinear rate. This also reveals the role of function heterogeneity on the convergence rate; (c) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity; and (d) A by-product of our analysis is a tuning recommendation for several existing (non-accelerated) distributed algorithms, yielding provably faster (worst-case) convergence rate for the class of problems under consideration. (II) Referring to lower complexity bounds, the proposed novel family of algorithms, when equipped with acceleration, are proved to be optimal, that is, they achieve convergence rate lower bounds. (III) Finally, to make the proposed algorithms practical, we break the synchronism in the agents’ updates: agents wake up and update without any coordination, using information only from immediate neighbors with unknown, arbitrary but bounded delays. Quite remarkably, even in the presence of asynchrony, the proposed algorithmic framework is proved to converge at a linear rate (resp. sublinear rate) when applied to strongly convex (resp. non strongly convex) optimization problems.</div>

Master‘s thesis deals with the theory of distributed optimization programs (next time just DOP), the suggestion and programme sample solver DOP and verification of the functionality of DOP ideas, principles and system architecture.

In the first part of this thesis, we propose a distributed consensus algorithm under multi-layer multi-group structure with communication time delays. It is proven that the consensus will be achieved in both time-varying and fixed communication delays. In the second part, we study the distributed optimization problem with a finite-time mechanism. It is shown that our distributed proportional-integral algorithm can exponentially converge to the unique global minimizer when the gain parameters satisfy the sufficient conditions. Moreover, we equip the proposed algorithm with a decentralized algorithm, which enables an arbitrarily chosen agent to compute the exact global minimizer within a finite number of time steps, using its own states observed over a successive time steps. In the third part, it is shown the implementation of accelerated distributed energy management for microgrids is achieved. The results presented in the thesis are corroborated by simulations or experiments.