Accelerated ADMM Variants for Distributed Optimization

QC 20260525

Abstract

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.

Link to DiVA