Distributed Optimization in Time-Varying Environments

Sammanfattning: Solving optimization problems in a distributed manner is critical in many systems. Many relevant systems are distributed in nature in the sense that they consist of autonomous agents that are to come to a joint decision based on a certain metric. In many cases, these agents may collect information independently and would therefore have to centralize all the data. In applications were this is not a viable approach distributed solutions are desirable.In this thesis, we study distributed optimization methods in time-varying environments. In the first part of the thesis, we consider optimization problems that evolve over time in a controlled manner. We propose the use of the Alternating Direction Method of Multipliers (ADMM) due to its flexibility in step-size selection. We establish ADMM's ability to follow an optimal point as it moves over time. In our set-up, a distributed variant of ADMM is allowed to perform a single iteration per problem change. Under smoothness assumptions on the objective and constraint functions we establishthat there exists a sufficiently small variation of the problem data for which we can guarantee that ADMM will be able to follow the optimal point in a decentralized manner. These conditions are less stringent than the conditions found in the literature. Later on, we introduce a stochastic model for the variation of the problem's data. Under some assumptions, we establish that decentralized ADMM is capable of remaining in a bounded mean square neighbourhood of a primal-dual optimal point. Introducing a stochastic model allows to us relax many of the requirements found in the literature, while still providing some guarantees. We provide with application examples and simulations for both scenarios.In the second part of the thesis we consider distributed optimization methods that converge over time-varying networks. We propose the first dual method to converge linearly on time-varying networks, in which we allow the networks to become disconnected. We establish that the method converges R-linearly and illustrate that under some circumstances it performs better than other state of the art methods, while, at the same time, cutting the required information exchanges in half. Since the proposed method is computationally quite expensive we propose a linearized and therefore computationally cheaper version of our method. Finally, we establish that the linearized version will also converge R-linearly on time-varying graphs and quantify the loss in convergence rate due to the approximation.