#Asymmetric FDLA Optimization

##Information

This work was done by Jose Antunes under the supervision of Prof. Joao Xavier at ISR - IST, University of Lisbon.

##Introduction

The work developed during my MSc Thesis aimed to optimize the performance of multiagent systems.

A multiagent system is a network of sensors that is linked by a communitation network. What is special about these systems is that they don't have a central computer that gathers all information and then broadcasts a result.

In this case, if we want to measure an average value, all sensors in the network have to cooperate and exchange messages, so that with an iterative algorithm they can reach an answer.

This process is called Distributed Linear Averaging.

To make sure we get to the answer as fast as possible, Boyd has published an article called Fastest Distributed Linear Averaging, that details the optimization problem to solve - the minimization os the spectral radius of the matrix that represents the network.

This matrix is special, because it encodes the topology of the graph, and the weight each communication link has between two sensors.

There are special constraints applied to this weight matrix that are detailed in Boyd's published article, as well as in my MSc Thesis.

About this work: With Boyd's work, we can only approach networks that are represented by symmetric weight matrices, as this makes their treatment by convex optimization easy.

With the work developed in this thesis, we have found and applied a series of convex approximations to the non-convex problem of minimizing the spectral radius for asymetric matrices.

These techniques allowed the creation of a convex problem that shows good results when applied to asymetric matrices.

The code in this repository is the same code I used to obtain my MSc Thesis results, under the section "Cool Down Algorithm".

##Requirements This project was built using:

1. Matlab - Version 8.5.0.197613 (R2015a)

• (check this using the "version" command)

2. CVX: Software for Disciplined Convex Programming - Version 2.1, Build 1107 (ad3582d)

• (check this using the "cvx_version" command)

##Contents

There are three folders inside this project.

1. algorithm

• Contains all GUI matlab code and the algorithm that solves the Asymmetric FDLA problem.

2. requiredFunctions

• Contains an additional function to verify if the graph is strongly connected.

3. requiredObjects

• Contains two matlab objects to make it easier to work with graphs and weight matrices.

##Instructions

Both the script and GUI use as input variable an adjacency matrix representing a graph.

You can find inside the script an example of one adjacency matrix. It is the same as the one shown here.

w =

 1     0     0     1     1     1     1     0     0     0
 0     1     0     0     1     0     0     0     0     1
 0     1     1     0     0     0     0     0     0     1
 1     0     0     1     0     0     0     0     1     0
 1     1     1     0     1     0     0     1     0     1
 1     0     0     0     0     1     1     0     0     0
 1     0     0     0     1     1     1     0     1     0
 0     0     0     0     1     0     0     1     0     0
 1     0     0     0     0     0     1     0     1     0
 0     1     0     0     0     0     0     0     0     1

This is the case of a directed graph with 10 nodes. Notice that all nodes consider the self-loop.

To run the algorithm call:

weightMatrix = CoolDownAlgorithm(w);

or

CoolDownGUI