On relative-error inertial-relaxed inexact proximal algorithms for monotone inclusion problems

Abstract

Neste trabalho, propomos e estudamos uma versão inercial subrelaxada e com erro relativo do método proximal extragradiente (HPE) de Sodolov e Svaiter para resolver problemas de inclusão monótono. Estudamos a convergência assintótica do método, bem como suas taxas de convergência não-assintótica global em termos de complexidade computacional em número de iterações. Analisamos o novo método sob condições mais flexíveis do que as existentes na literatura, tanto nos parâmetros de extrapolação quanto de erro relativo. A nova abordagem é aplicada a dois tipos de métodos do tipo \"forward-backward\" para resolver inclusões monótonas com determinada estrutura. Além disso, para resolver problemas de inclusão monótono envolvendo soma finita de operadores monótonos maximais, propomos e estudamos uma versão inercial relaxada om erro relativo do método \"projective splitting method (PSM)\" de Eckstein e Svaiter. O algoritmo proposto se beneficia de uma combinação de efeitos inerciais e de relaxação, controlada por parâmetros dentro de uma determinada faixa. Propomos condições suficientes sobre esses parâmetros (também estudamos a interação entre eles) para garantir a convergência fraca das sequências geradas por nosso algoritmo. Como uma aplicação do algoritmo proposto, derivamos um algoritmo inercial semelhante ao método \"alternating direction method of multipliers method (ADMM)\" com multiplos blocos.

Abstract: We propose and study an inertial under-relaxed version of the relative-error hybrid proximal extragradient (HPE) method of Sodolov and Svaiter for solving monotone inclusion problems. We study the asymptotic convergence of the method, as well as its nonasymptotic global convergence rates in terms of iteration-complexity. We analyze the new method under more flexible assumptions than existing ones, both on the extrapolation and on the relative-error parameters. The approach is applied to two types of forward-backward methods for solving structured monotone inclusions. For solving structured monotone inclusion problems involving the sum of finitely many maximal monotone operators, we propose and study an inertial-relaxed version of Eckstein and Svaiter projective splitting method. The proposed algorithm benefits from a combination of inertial and relaxation effects, which are both controlled by parameters within a certain range. We propose sufficient conditions on these parameters (as well as we study the interplay between them) to ensure weak convergence of sequences generated by our algorithm. As an application of the proposed algorithm we derive an inertial algorithm resembling the multi-block alternating direction method of multipliers (ADMM).