Um algoritmo de ponto proximal com efeitos de inércia e relaxação

Abstract

Dado um operador monótono maximal definido num espaço de Hilbert real, consideramos um Algoritmo Proximal com Inércia e Relaxação (RIPA) com cálculo exato do resolvente para resolver o Problema de Inclusão Monótona (MIP) associado. Esse algoritmo surge naturalmente da discretização do sistema contínuo Heavy Ball With Friction de Polyak considerando uma regularização de Yosida do operador original. Sob hipóteses apropriadas nos parâmetros e utilizando o Lema de Opial, mostramos que as sequências geradas pelo (RIPA) convergem fracamente para uma solução de (MIP). Começamos considerando parâmetros gerais na iteração, e ao final descrevemos classes particulares e de prática implementação que satisfazem as hipóteses para convergência. Esse algoritmo generaliza o clássico Algoritmo de Ponto Proximal (PPA), incorporando os efeitos de inércia e relaxação na tentativa de acelerar a convergência, em concordância com o Fast Gradient Method de Nesterov e o FISTA de Beck e Teboulle. Como casos particulares, resgatamos resultados de convergência para o Algoritmo Proximal com Relaxação e para o Algoritmo Proximal com Inércia, estabelecidos respectivamente por Eckstein e Bertsekas e por Alvarez e Attouch.

Abstract: Given a maximal monotone operator defined on a real Hilbert space, we consider a Relaxed Inertial Proximal Algorithm (RIPA) with exact resolvent calculation in order to solve the associated Monotone Inclusion Problem (MIP). This algorithm comes naturally from the discretization of the continuous system Heavy Ball With Friction of Polyak considering a Yosida regularization of the original operator. Under appropriate hypotheses on the parameters and invoking the Opial?s Lemma, we prove the weak convergence of the sequences generated by (RIPA) towards a solution of (MIP). We begin by considering general sequences of parameters, and at the end we describe particular classes with pratical implementation which satisfy the convergence hypotheses. This algorithm generalizes the classical Proximal Point Algorithm (PPA), adding the inertial and relaxation effects in the hope of obtaining faster convergence, in line with the Fast Gradient Method of Nesterov and FISTA of Beck and Teboulle. As particular cases, we recover convergence results for the Relaxed Proximal Algorithm and for the Inertial Proximal Algorithm, provided by Eckstein and Bertsekas and by Alvarez and Attouch respectively.