Abstract:
RESUMO: Nesta dissertação, inicialmente apresentamos o Algoritmo do Ponto Proximal sem
restrições para encontrar zeros de Operadores Monótonos Maximais (com a norma euclideana)
T : Rn Rn, que gera uma sequência fxkg Rn, da seguinte forma: seja x0 2 Rn,
xk 2 (I +
1
k
T)(xk+1),
ou seja,
xk+1 2 (I +
1
k
T)-1(xk),
onde f kg é uma sequência de números positivos satisfazendo
0 < k 6 ¯ ,
para algum ¯ > 0.
Mostraremos que a sequência fxkg gerada por este algoritmo converge para um zero de T.
Em seguida, substituindo a norma euclideana pela distância de Bregman apresentamos o
Algoritmo do Ponto Proximal com Distância de Bregman (Generalizado) para resolver o
Problema de Desigualdade Variacional VIP(T,C) (Variational Inequality Problem), que
é definido da seguinte forma: dado T : Rn Rn monótono maximal e C Rn um
conjunto fechado e convexo, o VIP(T,C) consiste de encontrar z 2 C tal que existe
u 2 T(z) satisfazendo
hu, x - zi > 0, 8 x 2 C.
O algoritmo gera uma sequência fxkg da seguinte forma: seja x0 2 C0 e xk 2 C0 defina
Tk : Rn Rn por
Tk( ) := T( ) + k@xDh( , xk)
e encontre xk+1 2 C0 tal que
0 2 Tk(xk+1).
iv
v
Equivalentemente,
xk+1 2 [@xDh( , xk) +
1
k
T]-1(xk),
ou ainda
k[rh(xk) - rh(xk+1)] 2 T(xk+1),
onde C0 é o interior de C.
Além disso, mostramos que a sequência fxkg gerada pelo algoritmo acima converge para
uma solução do VIP(T,C).
ABSTRACT: In this dissertation, we initially present the Proximal Point Algorithm without restrictions
to find zeros of Maximal Monotone Operators (with the Euclidean norm) T : Rn Rn,
that generates a sequence fxkg Rn, in the following way: given x0 2 Rn,
xk 2 (I +
1
k
T)(xk+1),
i.e.
xk+1 2 (I +
1
k
T)-1(xk),
where f kg is a sequence of positive numbers satisfying
0 < k 6 ¯ , for some ¯ > 0.
We show that the sequence fxkg generated by this algorithm converges to a zero of T.
Next, by substituting the Euclidean norm by the Bregman is distance, we present the
Proximal Point Algorithm with Bregman is distance (Generalized) to solve the Variational
Inequality Problem VIP(T,C), which is defined in the following way: given T : Rn Rn
maximal monotone and C Rn a closed and convex set, the VIP(T,C) consists of finding
z 2 C such that there is u 2 T(z) satisfying
hu, x - zi > 0, 8 x 2 C.
The algorithm generates a sequence fxkg in the following way: given x0 2 C0 e xk 2 C0
define
Tk : Rn Rn by
Tk( ) := T( ) + k@xDh( , xk)
and find xk+1 2 C0 such that
0 2 Tk(xk+1).
vi
vii
Equivalently,
xk+1 2 [@xDh( , xk) +
1
k
T]-1(xk),
or
k[rh(xk) - rh(xk+1)] 2 T(xk+1),
where C0 is the interior of C.
Moreover we show that the sequence fxkg generated by the above algorithm converges to
a solution of VIP(T,C).
