ALGORITMO DO PONTO PROXIMAL GENERALIZADO PARA O PROBLEMA DE DESIGUALDADE VARIACIONAL EM RN

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).