Shreyansh_MastersThesis_v4.pdf (1.05 MB)

Download file# Fast Tracking ADMM for Distributed Optimization and Convergence under Time-Varying Networks

thesis

posted on 06.05.2021, 12:17 authored by Shreyansh Rakeshkuma ShethiaShreyansh Rakeshkuma ShethiaDue to the increase in
the advances in wireless communication, there has been an increase in the use
of multi-agents systems to complete any given task. In various applications,
multi-agent systems are required to solve an underlying optimization problem to
obtain the best possible solution within a feasible region. Solving such
multi-agent optimization problems in a distributed framework preferable over
centralized frameworks as the former ensures scalability, robustness, and
security. Further distributed optimization problem becomes challenging when the
decision variables of the individual agents are coupled. In this thesis, a
distributed optimization problem with coupled constraints is considered, where
a network of agents aims to cooperatively minimize the sum of their local
objective functions, subject to individual constraints. This problem setup is
relevant to many practical applications like formation flying, sensor fusion,
smart grids, etc. For practical scenarios, where agents can solve their local
optimal solution efficiently and require fewer assumptions on objective
functions, the Alternating Direction Method of Multipliers(ADMM)-based approaches
are preferred over gradient-based approaches. For such a constraint coupled
problem, several distributed ADMM algorithms are present that guarantee
convergence to optimality but they do not discuss the complete analysis for the
rate of convergence. Thus, the primary goal of this work is to improve upon the
convergence rate of the existing state-of-the-art Tracking-ADMM (TADMM)
algorithm to solve the above-distributed optimization problem. Moreover, the
current analysis in literature does not discuss the convergence in the case of
a time-varying communication network. The first part of the thesis focuses on improving
the convergence rate of the Tracking-ADMM algorithm to solve the above-distributed
optimization problem more efficiently. To this end, an upper bound on the
convergence rate of the TADMM algorithm is derived in terms of the weight
matrix of the network. To achieve faster convergence, the optimal weight matrix
is computed using a semi-definite programming (SDP) formulation. The improved
convergence rate of this Fast-TADMM (F-TADMM) is demonstrated with a simple yet
illustrative, coupled constraint optimization problem. Then, the applicability
of F-TADMM is demonstrated
to the problem of distributed optimal control for trajectory generation of
aircraft in formation flight. In the second part of the thesis, the convergence
analysis for TADMM is extended while considering a time-varying communication
network. The modified algorithm is named as Time-Varying Tracking (TV-TADMM).
The formal guarantees on asymptotic convergence are provided with the help of
control system analysis of a dynamical system that uses Lyapunov-like theory.
The convergence of this TV-TADMM is demonstrated on a simple yet illustrative,
coupled constraint optimization problem with switching topology and is compared
with the fixed topology setting.