This doctoral thesis presents a comprehensive summary of research efforts with the aim of advancing the state-of-the-art in decentralized optimization. As modern distributed systems grow in scale and complexity, traditional optimization methods face significant bottlenecks. This work, presented as a compilation of five papers, specifically targets the Alternating Direction Method of Multipliers (ADMM). The central objective is to re-engineer ADMM to overcome the dual challenges of convergence latency and communication inefficiencies in peer-to-peer networks.  The first part of the thesis focuses on decentralization, convergence speed, and computational cost. While centralized ADMM algorithms struggle with scalability and bottlenecks, existing decentralized schemes rely on either excessive computations and messaging or completely sequential operations, causing a prolonged time required to reach convergence. To tackle these problems, we introduce two fast-converging decentralized ADMM algorithms. Our theoretical analysis confirms that our algorithms retain the classical convergence properties of centralized ADMM while maintaining a low per-node complexity of $O(1)$. Numerical simulations further demonstrate that our algorithms converge significantly faster than state-of-the-art decentralized implementations, providing clear conditions under which they outperform traditional benchmarks.  The second part of the thesis addresses the straggler problem, which arises from the conventional ADMM requirement for global synchronization, where faster nodes are forced to remain idle until the slowest nodes complete their local updates, impeding the progress of the entire network. Here, we introduce three algorithms to allow the system to remain productive even under single-point-of-failure scenarios or extreme hardware variance. The first algorithm achieves straggler-resilience by allowing the nodes to proceed to the next iteration even when one or more nodes have not provided an update for one or more iterations. The second algorithm is a decentralized version of the first algorithm. The second algorithm enforces fast convergence as well as robustness against stragglers and single points of failure through decentralized, asynchronous, and concurrent operations. The third algorithm extends the second algorithm by enforcing robustness against uncertainties with the help of a time-tracking scheme. Through theoretical analyses, we establish the convergence properties of our algorithms and show that our decentralized algorithms achieve a computational complexity of $O(1)$ for each worker node, whereas our centralized algorithm achieves a computational complexity of $O(N)$ for the central node and $O(1)$ for each of the remaining nodes. Through numerical simulations with various settings, we show that our algorithms have converged significantly faster than several state-of-the-art ADMM algorithms with well-established convergence properties.

The final part of the thesis extends these optimizations to highly volatile systems characterized by message dropouts and dynamic topologies. Here, we introduce two algorithms to adapt ADMM to dynamic systems, where new nodes may be added amidst the process at the same time as the system may encounter issues with stragglers and message dropouts. The algorithms achieve fast convergence and flexibility by allowing nodes to choose a step size that is best suited for their own system and by allowing the nodes to move on to the next iteration even when not all nodes have made an update for the current iteration. More importantly, these algorithms incorporate a contribution tracking mechanism to ensure consistency despite message loss. Furthermore, these algorithms enforce robustness against uncertainties by removing the need to predefine the waiting time or the minimum number of updates before moving to the next iteration. Here, an approximation mechanism is also introduced to give stragglers more time to compute their variables while the faster nodes move on to the next iteration.

To summarize, this thesis provides accelerated algorithms for fast convergence in distributed optimization, with solutions tailored for both large-scale and dynamic networks.

Denna doktorsavhandling presenterar en omfattande sammanfattning av forskningsinsatser som syftar till att främja den senaste tekniken inom decentraliserad optimering. I takt med att moderna distribuerade system växer i skala och komplexitet möter traditionella optimeringsmetoder betydande flaskhalsar. Detta arbete, som presenteras som en sammanställning av fem artiklar, riktar sig specifikt mot Alternating Direction Method of Multipliers (ADMM). Det centrala målet är att omkonstruera ADMM för att övervinna de dubbla utmaningarna med konvergenslatens och kommunikationsineffektivitet i peer-to-peer-nätverk.

Den första delen av avhandlingen fokuserar på decentralisering, konvergenshastighet och beräkningskostnad. Medan centraliserade ADMM-algoritmer lider av skalbarhetsproblem och flaskhalsar, förlitar sig existerande decentraliserade metoder antingen på omfattande beräkningar och kommunikation eller helt sekventiella operationer, vilket leder till långsammare konvergens. För att hantera dessa problem introducerar vi två snabbt konvergerande ADMM-algoritmer. Vår teoretiska analys bekräftar att dessa algoritmer behåller de klassiska konvergensegenskaperna hos centraliserad ADMM samtidigt som de bibehåller låg komplexitet på $O(1)$ per nod. Numeriska simuleringar visar vidare att våra algoritmer konvergerar betydligt snabbare än befintliga decentraliserade implementeringar.

Den andra delen av avhandlingen behandlar det klassiska problemet med eftersläntrare hos ADMM-algoritmer, där snabbare noder tvingas vänta på de långsammaste noderna på grund av det konventionella kravet på synkronisering i ADMM. Här introducerar vi tre algoritmer för att låta systemet förbli produktivt även under scenarier med en enda felpunkt eller extrem hårdvaruvarians. Den första algoritmen uppnår tolerans mot långsamma noder (eftersläntrare) genom att låta noderna fortsätta till nästa iteration även när en eller flera noder inte har tillhandahållit en uppdatering under en eller flera iterationer. Den andra algoritmen är en decentraliserad variant av den första algoritmen. Den tredje algoritmen utökar den andra algoritmen med ett tidsspårningsschema. Genom teoretiska analyser fastställer vi konvergensegenskaperna hos våra algoritmer och visar att våra decentraliserade algoritmer uppnår en beräkningskomplexitet på $O(1)$ för varje arbetsnod, medan vår centraliserade algoritm uppnår en beräkningskomplexitet på $O(N)$ för centralnoden och $O(1)$ per nod för de övriga noderna. Genom numeriska simuleringar med olika inställningar visar vi att våra algoritmer konvergerar betydligt snabbare än flera ADMM-algoritmer med väletablerade konvergensegenskaper.

Den sista delen av avhandlingen utökar dessa optimeringar till volatila system som kännetecknas av meddelandeförlust och dynamiska topologier. Här introducerar vi ytterligare två ADMM-algoritmer för dynamiska system, där nya noder kan ansluta sig mitt i processen samtidigt som systemet kan stöta på problem med eftersläntrare och meddelandeförlust. Dessa algoritmer är skapade för att uppnå snabb konvergens och flexibilitet genom att låta noder välja en stegstorlek som passar bäst för det egna systemet och genom att låta noderna gå vidare till nästa iteration även om inte alla noder har gjort en uppdatering för den aktuella iterationen. Ännu viktigare är att dessa algoritmer har ett identifieringssystem för att säkerställa konvergens trots meddelandeförlust. Algoritmerna upprätthåller även robusthet mot osäkerheter genom att ta bort behovet av att fördefiniera väntetiden eller det minsta antalet uppdateringar innan man går vidare till nästa iteration, genom ett tidsspårningsschema inspirerat av resultaten från den andra delen. Här har även en approximationsmekanism introducerats för att ge mer tid åt eftersläntrarna att utföra sina beräkningar medan de snabbare noderna går vidare till nästa iteration.

Sammanfattningsvis tillhandahåller denna avhandling accelererade algoritmer för snabb konvergens vid distribuerad optimering, med lösningar anpassade för såväl storskaliga som dynamiska nätverk.