A Consensus Approach to Distributed Convex Optimization in Multi-Agent Systems

In questa tesi viene affrontato il problema dell'ottimizzazione distribuita non vincolata di funzioni convesse. Lo scenario è costituito da una rete di agenti interconnessi, ognuno dei quali è dotato di una funzione costo locale convessa ed è soggetto a vincoli di comunicazione. Ogni agente vuole collaborare per calcolare il minimo della somma dei costi locali. Viene proposta una soluzione che combina algoritmi di average consensus con concetti di separazione delle scale temporali, propri della teoria del controllo non lineare. Tale strategia, denotata come Newton-Raphson Consensus, si dimostra convergere globalmente al minimo richiesto, sotto opportune ipotesi. Intuitivamente, l'algoritmo permette agli agenti di calcolare in maniera distribuita e di aggiornare sequenzialmente una direzione approssimata alla Newton-Raphson, tramite specifici rapporti di average consensus. Viene proposta una versione sincrona del Newton-Raphson Consensus, validata sia per funzioni scalari che vettoriali, proponendo nel secondo caso alcune strategie alternative volte a bilanciare le prestazioni, in termini di requisiti computazionali e di comunicazione, con una adeguata velocità di convergenza. Vengono presentate prove analitiche di convergenza e simulazioni numeriche che evidenziano come la velocità di convergenza del Synchronous Newton-Raphson Consensus è comparabile con strategie di ottimizzazione alternative quali l'Alternating Direction Method of Multipliers, il Distributed Subgradient Method e il Distributed Control Method. La trattazione si completa con l'analisi della velocità di convergenza del Synchronous Newton-Raphson Consensus, comparata con quella di un Gradient Descent Consensus, sotto l'ipotesi semplificativa di funzioni costo quadratiche. Vengono derivate condizioni sufficienti che garantiscono la convergenza di tali algoritmi. Da queste condizioni si ottengono espressioni in forma chiusa che possono essere utilizzate per regolare i parametri che caratterizzano gli algoritmi e per massimizzare la velocità di convergenza. Si evidenzia che nonostante queste formule siano derivate assumendo funzioni di costo (locali) quadratiche, esse possono essere usate come metodologie di riferimento per la regolazione dei parametri degli algoritmi in situazioni generali. Infine, viene proposta una versione asincrona del Newton-Raphson Consensus. Oltre ad avere una ridotta complessità computazionale e minimi requisiti di comunicazione, questa tecnica richiede poca coordinazione tra gli agenti e si mantiene valida in topologie tempo-varianti. Ancora una volta, viene dimostrato analiticamente, sotto opportune ipotesi, che l'Asynchronous Newton-Raphson Consensus ha proprietà di convergenza locali o globali. Mediante simulazioni numeriche vengono corroborati tali risultati e vengono confrontate le prestazioni di tale algoritmo con altri metodi di ottimizzazione distribuita quali l'Asynchronous Fast Newton-Raphson Consensus, l'Asynchronous Distributed Subgradient Method, l'Asynchronous Alternating Direction Method of Multipliers e il Pairwise Equalizing Method.