Abstrakt. Detta dokument introducerar en parallell och distribuerad utvidgning till den alternerande riktningsmetoden av multiplikatorer (ADMM) för att lösa konvexa problem: Algoritmen dekomponerar det ursprungliga problemet i N mindre subproblem och löser dem parallellt vid varje iteration. Denna Jacobian-typ algoritm är väl lämpad för distribuerade datorer och är särskilt attraktiv för att lösa vissa storskaliga problem. I detta dokument presenteras några nya resultat. För det första visar det att utvidga ADMM rakt från den klassiska Gauss-Seidel inställning till Jacobian inställning, från 2 block till N block, kommer att bevara konvergens om matriser Ai är ömsesidigt nära-ortogonal och har full kolumn-rank. För det andra, för allmänna matriser Ai, föreslås i detta dokument att proximala termer av olika slag läggs till underproblemen N så att underproblemen kan lösas på ett flexibelt och effektivt sätt och algoritmen konvergerar globalt i en takt av o(1/k). För det tredje införs en enkel teknik för att förbättra vissa befintliga konvergensnivåer från O(1/k) till o(1/k). I praktiken är vissa villkor i våra konvergensteoremer konservativa. Därför inför vi en strategi för dynamisk anpassning av parametrarna i algoritmen, vilket i praktiken leder till en betydande ökning av konvergensen. Numeriska resultat presenteras för att visa effektiviteten av den föreslagna metoden i jämförelse med flera befintliga parallella algoritmer. Vi implementerade vår algoritm på Amazon EC2, en on-demand public computing cloud, och rapportera dess prestanda på mycket storskalig basis jakt problem med distribuerade data.
Slutligen uppdaterar Proximal Jacobian ADMM (PJADMM) variablerna parallellt samtidigt som konvergenskvoten o(1/k) uppnås utan villkor för begränsningarna REF.
Parallel Multi-Block ADMM with o(1/k) Convergence
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Mathematics', 'Computer Science']}