Optimization Algorithms over Distributed Systems
- Author(s): Moradian, Hossein
- Advisor(s): Kia, Solmaz SK
- et al.
This dissertation contributes toward design, convergence analysis and improving the performance of the current state of knowledge on central and distributed solutions for in-network optimization algorithms. We investigate how mathematical tools can be utilized to develop and analyze distributed optimization algorithms that respect the restrictions inherent to communication and address computational concerns in smart network operation. The results of this dissertation will facilitate the realization and adoption of optimal in-network solutions in many important applications, such as machine learning, smart grids, robotics, sensor coordination and distributed data regression in different sectors.
We develop our results by studying the performance of consensus-based algorithm as a common approach to solve the optimization problems in the decentralized way. We first examine the robustness of a dynamic average consensus algorithm to communication delay over strongly connected and weight-balanced (SCWB) digraphs. For such algorithm, in both its continuous-time and discrete-time implementations, we characterize the admissible communication delay range and study the effect of the delay on the rate of convergence and the tracking error bound. Next, we investigate comprehensive study of a long observed phenomenon of increase in the stability margin and so the rate of convergence of a class of linear systems due to time delay. Using our result, we propose an accelerated algorithm for dynamic and static average consensus problem by using outdated feedback. Such algorithm enables agents over the network to achieve faster agreement on a certain quantity.
Our study on optimization algorithm design includes proposing a distributed solution for a constrained convex optimization problem over a network of clustered agents each consists of a set of sub-agents. Our proposed distributed algorithm is a novel continuous-time algorithm that is linked to the augmented Lagrangian approach. We demonstrate our results via optimal resource allocation problem for smart grids, and an optimal multi-sensor deployment problem.
We also propose a Hessian-based algorithm for the optimization problem over a network. We demonstrate that such algorithm has a comparable convergence rate to that of the continuous-time Newton-Raphson method, however structurally, it is amenable to a more efficient distributed implementation. We show the effectiveness of our algorithm for a distributed classification problem over a network .Finally, we develop an algorithm to track the optimal trajectory of the optimization problem with time-varying cost function. Our algorithm provides central solution with a fast con-vergence to the sufficiently small enough neighborhood of the exact optimizer without using second-order information of the cost function.