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

In this thesis we address the problem of distributed unconstrained convex optimization under separability assumptions, i.e., the framework where a network of agents, each endowed with local private convex cost and subject to communication constraints, wants to collaborate to compute the minimizer of the sum of the local costs. We propose a design methodology that combines average consensus algorithms and separation of time-scales ideas. This strategy is proven, under suitable hypotheses, to be globally convergent to the true minimizer. Intuitively, the procedure lets the agents distributedly compute and sequentially update an approximated Newton-Raphson direction by means of suitable average consensus ratios. We consider both a scalar and a multidimensional scenario of the Synchronous Newton-Raphson Consensus, proposing some alternative strategies which trade-off communication and computational requirements with convergence speed. We provide analytical proofs of convergence and we show with numerical simulations that the speed of convergence of this strategy is comparable with alternative optimization strategies such as the Alternating Direction Method of Multipliers, the Distributed Subgradient Method and Distributed Control Method. Moreover, we consider the convergence rates of the Synchronous Newton-Raphson Consensus and the Gradient Descent Consensus under the simplificative assumption of quadratic local cost functions. We derive sufficient conditions which guarantee the convergence of the algorithms. From these conditions we then obtain closed form expressions that can be used to tune the parameters for maximizing the rate of convergence. Despite these formulas have been derived under quadratic local cost functions assumptions, they can be used as rules-of-thumb for tuning the parameters of the algorithms. Finally, we propose an asynchronous version of the Newton-Raphson Consensus. Beside having low computational complexity, low communication requirements and being interpretable as a distributed Newton-Raphson algorithm, the technique has also the beneficial properties of requiring very little coordination and naturally supporting time-varying topologies. Again, we analytically prove that under some assumptions it shows either local or global convergence properties. Through numerical simulations we corroborate these results and we compare the performance of the Asynchronous Newton-Raphson Consensus with other distributed optimization methods.

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.