Distributed decision making with application to energy systems

This thesis addresses decision making problems in systems composed of multiple agents which are jointly aiming at optimizing performance, subject to some coupling in their decisions. Centralized solutions of the resulting optimization problem pose several difficulties, ranging from being computationally intensive, to forcing agents to disclose their private information to some central unit. This calls for alternative distributed resolution strategies exploiting the agents computation and communication capabilities. Global optimization problems that are solvable via distributed strategies usually exhibit an almost separable structure with a distinct coupling feature, like a common decision vector (decision-coupled problems) or a set of constraints coupling the individual decision variables of different agents (constraint-coupled problems). We consider a system composed of heterogeneous agents with their own objective function and constraint set, communicating through a possibly time-varying communication network. For each class of problems, we devise a new synchronous iterative scheme that guarantees convergence to an optimal solution of the global problem while requiring the agents to exchange only a limited amount of information with their neighbors, maintaining their objective function and local constraint set private. In both set-ups we broaden the class of problems which can be solved via a distributed approach, since our algorithms require milder conditions than other approaches in the literature. We then focus on linear constraint-coupled problems, but with the additional difficulty that some decision variables are restricted to assume discrete values only, which makes the problem combinatorial. We provide a decentralized iterative algorithm that decomposes the problem into smaller ones and is able to determine, in a finite number of iterations, a solution which is feasible, though suboptimal, for the global problem. The proposed approach improves over state of the art results in terms of finite time computability and suboptimality bound. In practical applications, it is often the case that decisions are taken in presence of uncertainty. Ignoring the uncertainty may lead to infeasible solutions. We tackle the problem of finding a distributed solution which is robust against the uncertainty via a randomized sample-based method called scenario approach, extending its probabilistic feasibility guarantees to a distributed setting where agents can use their local uncertainty instances without sharing them with the other agents. All theoretical developments in the thesis are supported by numerical evidence on problems related to energy systems.

In questa tesi si considerano sistemi formati da più agenti, ognuno con una sua funzione di costo da minimizzare, che sono però vincolati nella loro scelta delle variabili decisionali perché esse sono condivise (problemi con decisione comune) oppure perché sono distinte ma devono soddisfare un vincolo congiunto, legato per esempio all’utilizzo di una risorsa condivisa di capacità finita (problemi con vincoli di accoppiamento). Una soluzione centralizzata al problema di ottimizzazione vincolata che ne deriva comporta una serie di problematiche legate all'eccessivo carico computazionale e alla riservatezza delle informazioni degli agenti coinvolti. Da queste considerazioni nasce la necessità di sviluppare soluzioni di tipo distribuito che sfruttino le capacità di calcolo e di comunicazione con i propri vicini di ogni singolo agente. I problemi con decisione comune e quelli con vincoli di accoppiamento che consideriamo possiedono una struttura parzialmente separabile, che li rende potenzialmente trattabili con tecniche di ottimizzazione distribuita. Sia per i problemi con decisione comune, sia per i problemi con vincoli di accoppiamento, proponiamo una nuova procedura iterativa che, se eseguita in modo sincrono da tutti gli agenti, garantisce la convergenza delle soluzioni locali a una soluzione del problema globale e, al contempo, limita lo scambio di informazioni tra gli agenti mantenendo riservate sia le funzioni obiettivo, sia i vincoli locali. La procedura proposta si applica a sistemi composti da agenti eterogenei, ognuno con la propria funzione obiettivo e il proprio insieme di vincoli locali, che si scambiano informazioni attraverso una rete tempo-variante. Essa amplia le classi di problemi che possono essere risolti in modo distribuito, in quanto richiede ipotesi più lasche rispetto ad altre tecniche presenti in letteratura. Nella tesi si tratta poi il caso di problemi lineari (quindi più semplici) con vincoli di accoppiamento, ma con la difficoltà aggiuntiva che alcune variabili decisionali sono discrete. Questo rende il problema combinatorio e, di conseguenza, più complesso da risolvere. Per questa classe proponiamo un algoritmo decentralizzato che scompone il problema di partenza in sotto-problemi e determina, in un numero finito di iterazioni, una soluzione ammissibile, anche se sub-ottima, per il problema globale. Un'implementazione decentralizzata, a differenza di una distribuita, richiede la presenza di un'unità centrale che comunica con tutti gli agenti del sistema, ma che però si limita a svolgere un ruolo di coordinamento per la rete. La tecnica proposta si dimostra essere preferibile rispetto ad altri approcci presenti in letteratura sia perché termina in un numero finito di iterazioni, sia perché fornisce una soluzione migliore in termini di indice di prestazione per il sistema complessivo. In un contesto reale, gli agenti operano spesso in un ambiente affetto da incertezza e ignorare l'incertezza potrebbe portare a decisioni non ammissibili. Partendo da questa osservazione, abbiamo sviluppato uno schema di ottimizzazione distribuita che è in grado di trovare una soluzione robusta rispetto all'incertezza. Lo schema proposto si basa su una tecnica randomizzata per l’ottimizzazione, denominata approccio a scenario. Nello specifico, abbiamo esteso le garanzie probabilistiche dell’approccio a scenario sull'ammissibilità della soluzione ad un contesto distribuito, che non prevede lo scambio dei campioni tra gli agenti, mantenendone quindi la riservatezza. Tutte le tecniche sviluppate nella tesi sono corroborate da simulazioni numeriche che si riferiscono ad applicazioni realistiche dell’ottimizzazione distribuita a sistemi energetici.