Methods for Large-Scale Distributed Optimization

mansoori, fatemeh

doi:https://doi.org/10.21985/n2-c52z-x142

Work

Methods for Large-Scale Distributed Optimization

Public

Download PDF

Download All Files (.zip)

With the growing size of networks and datasets and the lack of centralized access to information, distributed control and optimization become inevitable. In the first part of this thesis, we develop an asynchronous Newton-based distributed optimization algorithm and analyze its convergence properties. Our algorithm benefits from the fast convergence properties of second-order methods and also asynchronous implementation, which removes the need for a central coordinator, reduces the synchronization wait and allows some agents to compute faster and execute more iterations. We prove that for strongly convex objective functions, our algorithm achieves a global linear and local quadratic rate of convergence. This result is the first superlinear convergence rate guarantee for asynchronous distributed optimization algorithms. In the second part of this thesis, we develop a flexible framework of first-order primal-dual algorithms (FlexPD). The novelty in the design of flexible primal updates enables us to control the trade-off between the complexity and performance of the primal-dual algorithms. Our proposed framework can be customized for various applications with different computation and communication limitations. For strongly convex and Lipschitz gradient objective functions, we establish linear convergence of our proposed algorithms to the optimal solution. Simulation results confirm the superior performance of our algorithm compared to the existing methods. In the last part of this thesis, we focus on designing second-order primal-dual algorithms. In our algorithm, the primal variable is updated through a single Newton step and an approximation of the Newton step is used in the dual space. We use matrix splitting techniques to compute this approximation and we establish a linear rate of convergence for quadratic strongly convex objective functions. Numerical experiments confirm the superior performance of second-order primal-dual methods to first-order algorithms.

Creator