On the Spingarn's partial inverse method: inexact versions, convergence rates and applications to operator splitting and optimization

Abstract

Neste trabalho, propomos e estudamos a complexidade computacional (em número de iterações) de uma versão inexata do método das inversas parciais de Spingarn. Os principais resultados de complexidade são obtidos através de uma análise do método proposto no contexto do hybrid proximal extragradient (HPE) method de Solodov e Svaiter, para o qual resultados decomplexidade pontual e ergódica foram obtidos recentemente por Monteiro e Svaiter. Como aplicações, propomos e analisamos a complexidade computacional de um algoritmo inexato de decomposição -- que generaliza o algoritmo de decomposição de Spingarn -- e de um algoritmo paralelo do tipo forward-backward para otimização convexa com múltiplos termos na função objetivo. Além disso, mostramos que o algoritmo scaled proximal decomposition on the graph of a maximal monotone operator (SPDG), originalmente introduzido e estudado por Mahey, Oualibouch e Tao (1995), pode ser analisado através do formalismo das inversas parciais de Spingarn. Mais precisamente, mostramos que sob as hipóteses consideradas por Mahey, Oualibouch and Tao, a inversa parcial de Spingarn (do operador monótono maximal que define o problema em consideração) é um operador fortemente monótono, o que permite empregar resultados recentes sobre convergência e complexidade computational de métodos proximais para operadores fortemente monótonos. Ao fazer isso, obtemos adicionalmente uma convergência potencialmente mais rápida para o algorítmo SPDG e um limite superior mais preciso sobre o número de iterações necessárias para alcançar tolerâncias prescritas, especialmente para problemas mal-condicionados.

Abstract : In this work, we propose and study the iteration-complexity of an inexact version of the Spingarn's partial inverse method. Its complexity analysis is performed by viewing it in the framework of the hybrid proximal extragradient (HPE) method, for which pointwise and ergodic iteration-complexity has been established recently by Monteiro and Svaiter. As applications, we propose and analyze the iteration-complexity of an inexact operator splitting algorithm -- which generalizes the original Spingarn's splitting method -- and of a parallel forward-backward algorithm for multi-term composite convex optimization. We also show that the scaled proximal decomposition on the graph of a maximal monotone operator (SPDG) algorithm introduced and analyzed by Mahey, Oualibouch and Tao (1955) can be analyzed within the original Spingarn's partial inverse framework. %The SPDG algorithm generalizes the Spingarn's partial inverse method by allowing scaling factors, a key strategy for speeding up the convergence of numerical algorithms. We show that under the assumptions considered by Mahey, Oualibouch and Tao, the Spingarn's partial inverse of the underlying maximal monotone operator is strongly monotone, which allows one to employ recent results on the convergence and iteration-complexity of proximal point type methods for strongly monotone operators. By doing this, we additionally obtain a potentially faster convergence for the SPDG algorithm and a more accurate upper bound on the number of iterations needed to achieve prescribed tolerances, specially for ill-conditioned problems.