Motiverad av big data applikationer, första ordningen metoder har varit mycket populär under de senaste åren. Men naiva gradientmetoder konvergerar i allmänhet långsamt. Därför har stora ansträngningar gjorts för att påskynda olika första ordningens metoder. I detta dokument föreslås två påskyndade metoder för att lösa strukturerad linjärt begränsad konvex programmering, där vi antar sammansatta konvexa mål som är summan av en differentierad funktion och en möjligen icke-differentierad. Den första metoden är den accelererade linjäriserade utökade Lagrangian metoden (LALM). Vid varje uppdatering till den primära variabeln, det tillåter linjärisering till den differentierade funktionen och även den utökade termen, och därmed möjliggör det enkla subproblem. Förutsatt att konvexiteten bara är svag visar vi att LALM äger O(1/t) konvergens om parametrarna hålls fasta under alla iterationer och kan accelereras till O(1/t 2 ) om parametrarna anpassas, där t är antalet totala iterationer. Den andra metoden är den accelererade lineariserade växelriktningsmetoden för multiplikatorer (LADMM). Utöver den sammansatta konvexiteten utgår den dessutom från två blocks struktur på målet. Annorlunda från klassisk ADMM, vår metod tillåter linjärisering till målet och även förstärkt term för att göra uppdateringen enkel. Om man antar stark konvexitet på en blockvariabel, visar vi att LADMM också har O(1/t 2 ) konvergens med adaptiva parametrar. Detta resultat är en betydande förbättring jämfört med den i [Goldstein et. al, SIIMS'14], som kräver stark konvexitet på både blockvariabler och ingen linjärisering till den objektiva eller förstärkta termen. Numeriska experiment utförs på quadratic programmering, bild denoising, och stöd vektor maskin. De föreslagna påskyndade metoderna jämförs med icke-accelererade metoder och även befintliga påskyndade metoder. Resultaten visar att accelerationen är giltig och att de föreslagna metoderna har en överlägsen prestanda jämfört med befintliga metoder.
Inom ALM-ramverket utför REF en enda proximal gradientuppdatering till primalvariabel vid varje iteration och etablerar O(ε −1 ) komplexitetsresultat för att få en ε-optimal lösning för affinely begränsade sammansatta konvexa program.
Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}