Den alternerande riktningsmetoden för multiplikatorer (ADMM) används i stor utsträckning för att lösa strukturerade konvexa optimeringsproblem på grund av dess överlägsna praktiska prestanda. På den teoretiska sidan visades emellertid ett motexempel [7] som indikerar att multiblockets ADMM för att minimera summan av N (N ≥ 3) konvexa funktioner med N-blockvariabler kopplade till linjära begränsningar kan skilja sig åt. Det är därför av stort intresse att undersöka ytterligare tillräckliga villkor på insatssidan som kan garantera konvergens för multiblockerad ADMM. De befintliga resultaten kräver vanligtvis den starka konvexiteten på delar av målet. I detta dokument presenterar vi konvergens- och konvergensresultat för de multiblockerade ADMM som tillämpas för att lösa vissa N-block (N ≥ 3) konvexa minimeringsproblem utan att kräva stark konvexitet. Specifikt, Vi bevisar följande två resultat: (1) multi-block ADMM returnerar en multi-block ADMM en optimal lösning inom O(1/ på 2 ) iterationer genom att lösa en associerad perturbation till det ursprungliga problemet; (2) multi-block ADMM returnerar en -optimal lösning inom O(1 /) iterationer när det tillämpas för att lösa ett visst delningsproblem, under förutsättning att den utökade Lagrangian funktionen uppfyller Kurdyka-Lojasiewicz egendom, som i huvudsak täcker de flesta konvexa optimeringsmodeller utom för vissa patologiska fall.
I REF visade författarna att multiblock ADMM kan uppnå -optimala lösningar inom O(1/2) iterationer genom att lösa en modifierad version av det ursprungliga problemet, och whitin O(1/ ) iterationer när det tillämpas på vissa delningsproblem som beror på egenskaperna hos den förstärkta Lagrangian funktionen.
Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Mathematics', 'Computer Science']}