ads:
Universidade Federal do Piauí
Centro de Ciências da Natureza
Pós-Graduação em Matemática
Mestrado em Matemática
Algoritmo do Ponto Proximal Generalizado para o
Problema de Desigualdade Variacional em R
n
João Santos Andrade
Teresina - 2010
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
João Santos Andrade
Dissertação de Mestrado:
Algoritmo do Ponto Proximal Generalizado para o Problema de
Desigualdade Variacional em R
n
Dissertação submetida à Coordenação do
Curso de Pós-Graduação em Matemática,
da Universidade Federal do Piauí, como
requisito parcial para obtenção do grau
de Mestre em Matemática.
Orientador:
Prof. Dr. Jurandir de Oliveira Lopes
Teresina - 2010
ads:
Algoritmo do Ponto Proximal Generalizado para o Problema de
Desigualdade Variacional em R
n
Teresina - 2010
Dedico este trabalho a meus pais Nivaldo e Maria
Francisca, a minha esposa Elcilene, a meus irmãos
e irmãs (Franklivaldo, Liana, Walkiria, Niviane, Vâ-
nia, Liziane e Nivaldo Filho), a meu avô Raimundo
e minha avó Angelita (In memorian).
Agradecimentos
Agradeço primeiramente a Deus pela vida e por ter me dado força para vencer as barreiras.
Aos meus pais Nivaldo e Maria Francisca pelo apoio e incentivo nessa conquista. A meus
irmãos, irmãs, tios, primos e meu avô Raimundo que sempre acreditaram em mim.
A minha esposa Elcilene pelo apoio, carinho, amor, paciência e incentivo.
A todos os meus amigos em especial Luís Carlos (irmão), Aurineide (grande incenti-
vadora), Claudio, Márcia, Julimar, Everaldo, Sulimery, Hélson, Jociel, Edivan, Fábio,
Sandra, Diego (Parnaíba), Hudson, Anderson, Yuri, Rogério, Romeu, Diego (Barão),
Déborah e Marciana pela amizade e incentivo. E todos os amigos do mestrado Gilberto,
Daniel, Venâncio, Italo, Pedro, Domingos, João Carlos, Arimatéia, Renan e Cleyton pela
amizade, solidariedade e companheirismos.
Ao professor Jurandir de Oliveira Lopes pela escolha do tema, orientação, paciência e
compreensão.
Ao professor João Xavier pelas orientações, sugestões e incentivo. Aos professores Rolando
Garciga e Sissy por terem participado da banca e pelas correções e sugestões.
A todos os professores e funcionários do departamento de matemática.
A CAPES pelo apoio financeiro.
ii
iii
“O senhor é meu pastor: nada me faltará.
Deitar-me faz me em verdes pastos, guia-
me mansamente a águas tranquilas. ... ".
Salmo 23.
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 eucli-
deana) T : R
n
⇒ R
n
, que gera uma sequência {x
k
} ⊂ R
n
, da seguinte forma: seja x
0
∈ R
n
,
x
k
∈ (I +
1
λ
k
T)(x
k+1
),
ou seja,
x
k+1
∈ (I +
1
λ
k
T)
−1
(x
k
),
onde {λ
k
} é uma sequência de números positivos satisfazendo
0 < λ
k
¯
λ,
para algum
¯
λ > 0.
Mostraremos que a sequência {x
k
} 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 : R
n
⇒ R
n
monótono maximal e C ⊂ R
n
um
conjunto fechado e convexo, o VIP(T , C) consiste de encontrar z ∈ C tal que existe
u ∈ T(z) satisfazendo
u, x − z 0, ∀ x ∈ C.
O algoritmo gera uma sequência {x
k
} da seguinte forma: seja x
0
∈ C
0
e x
k
∈ C
0
defina
T
k
: R
n
⇒ R
n
por
T
k
(·) := T(·) + λ
k
∂
x
D
h
(·, x
k
)
e encontre x
k+1
∈ C
0
tal que
0 ∈ T
k
(x
k+1
).
iv
v
Equivalentemente,
x
k+1
∈ [∂
x
D
h
(·, x
k
) +
1
λ
k
T]
−1
(x
k
),
ou ainda
λ
k
[∇h(x
k
) − ∇h(x
k+1
)] ∈ T(x
k+1
),
onde C
0
é o interior de C.
Além disso, mostramos que a sequência {x
k
} 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 : R
n
⇒ R
n
,
that generates a sequence {x
k
} ⊂ R
n
, in the following way: given x
0
∈ R
n
,
x
k
∈ (I +
1
λ
k
T)(x
k+1
),
i.e.
x
k+1
∈ (I +
1
λ
k
T)
−1
(x
k
),
where {λ
k
} is a sequence of positive numbers satisfying
0 < λ
k
¯
λ, for some
¯
λ > 0.
We show that the sequence {x
k
} 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 : R
n
⇒ R
n
maximal monotone and C ⊂ R
n
a closed and convex set, the VIP(T , C) consists of finding
z ∈ C such that there is u ∈ T (z) satisfying
u, x − z 0, ∀ x ∈ C.
The algorithm generates a sequence {x
k
} in the following way: given x
0
∈ C
0
e x
k
∈ C
0
define
T
k
: R
n
⇒ R
n
by
T
k
(·) := T (·) + λ
k
∂
x
D
h
(·, x
k
)
and find x
k+1
∈ C
0
such that
0 ∈ T
k
(x
k+1
).
vi
vii
Equivalently,
x
k+1
∈ [∂
x
D
h
(·, x
k
) +
1
λ
k
T]
−1
(x
k
),
or
λ
k
[∇h(x
k
) − ∇h(x
k+1
)] ∈ T (x
k+1
),
where C
0
is the interior of C.
Moreover we show that the sequence {x
k
} generated by the above algorithm converges to
a solution of VIP(T , C).
Sumário
Resumo iv
Abstract vi
Introdução 1
1 Noções Preliminares 4
1.1 Existência de Soluções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Conjuntos Convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Funções Convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Subgradiente de uma Função . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Funções Convexas com valores em R ∪ {+∞} . . . . . . . . . . . . . . . . . 15
1.6 Função Conjugada de uma Função Convexa . . . . . . . . . . . . . . . . . 18
1.7 Funções e Distâncias de Bregman . . . . . . . . . . . . . . . . . . . . . . . 22
2 Operadores Monótonos 25
2.1 Operadores Monótonos e Monótonos Maximais . . . . . . . . . . . . . . . . 25
2.2 Operadores Paramonótonos . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3 Operadores Pseudomonótonos . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 O Algoritmo do Ponto Proximal 34
3.1 O Algoritmo do Ponto Proximal para Operadores
Monótonos Maximais(APPOMM) . . . . . . . . . . . . . . . . . . . . . . . 34
4 Algoritmo do Ponto Proximal com Distâncias de Bregman para o Pro-
blema de Desigualdade Variacional 40
4.1 Problema de Desigualdade Variacional . . . . . . . . . . . . . . . . . . . . 40
viii
Sumário ix
4.2 Algoritmo do Ponto Proximal Generalizado para o VIP(T , C) . . . . . . . 41
A O Algoritmo do Ponto Proximal 48
A.1 O Algoritmo do Ponto Proximal em R
n
. . . . . . . . . . . . . . . . . . . . 48
A.2 O Algoritmo do Ponto Proximal com Distâncias de
Bregman(APPDB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Referências Bibliográficas 54
Introdução
Dada uma função f : R
n
→ R convexa e limitada inferiormente, o problema de otimização
convexa é definido por
min
x∈R
n
f(x). (1)
Quando x está restrito a um conjunto convexo e fechado C ⊂ R
n
, obtemos o problema de
otimização convexa restrito
min
x∈C
f(x). (2)
Utilizando o subdiferencial ∂f de f (ver Definição 1.9 ), podemos escrever o problema
(1) e (2) respectivamente, da seguinte forma
Encontrar x
∗
∈ R
n
, tal que 0 ∈ ∂f(x
∗
); (3)
e
Encontrar x
∗
∈ C, tal que existe u ∈ ∂f(x
∗
) satisfazendo
u, y − x
∗
0, (4)
para todo y ∈ C.
Quando f é uma função convexa e semicontínua inferiormente, temos que ∂f : R
n
⇒ R
n
é
um operador monótono maximal (ver Teorema 2.2). Assim, obtemos extensões naturais
dos problemas (3) e (4), substituíndo o operador ∂f por qualquer outro operador monótono
maximal T : R
n
⇒ R
n
da seguinte maneira
Encontrar x
∗
∈ R
n
, tal que 0 ∈ T (x
∗
); (5)
e
Encontrar x
∗
∈ C tal que existe u ∈ T (x
∗
) satisfazendo
u, y − x
∗
0, (6)
1
Sumário 2
para todo y ∈ C, respectivamente.
Desta forma, o problema (5) associado a um operador monótono maximal, é o problema de
encontrar zeros de T . O problema (6), é chamado o Problema de Desigualdade Variacional
para o operador T no conjunto C, o qual denotamos por VIP(T, C).
Faremos agora uma descrição do conteúdo dos capítulos desta dissertação.
No capítulo 1, apresentamos as definições e resultados de Análise Convexa, funções de
Bregman e Distância de Bregman que são utilizados no decorrer da dissertação.
O capítulo 2 contém definições e resultados da teoria de Operadores Monótonos. Além
disso, mostramos que o subdiferencial ∂f de uma função convexa é um operador Monótono
Maximal, Paramonótono e Pseudomonótono.
No capítulo 3, apresentamos o Algoritmo do Ponto Proximal para Operadores Monótonos
Maximais para resolver o problema (5). O qual gera uma sequência {x
k
}, para x
0
∈ R
n
,
da seguinte maneira
0 ∈ T (x
k+1
) + λ
k
(x
k+1
− x
k
), (7)
equivalentemente
x
k
∈ (I +
1
λ
k
T)(x
k+1
), (8)
ou seja
x
k+1
∈ (I +
1
λ
k
T)
−1
(x
k
), (9)
onde {λ
k
} é uma sequência de números positivos satisfazendo
0 < λ
k
¯
λ, (10)
para algum
¯
λ > 0 e é utilizado a norma Euclideana.
Mostraremos que a sequência gerada por (7) − (10) converge a uma solução do problema
(5), ou seja, a um zero de T sempre que o problema possuir soluções.
Finalmente, no capítulo 4 apresentamos o Algorimo do Ponto Proximal com distância de
Bregman para o VIP(T , C), o qual gera uma sequência {x
k
} definida por
x
0
∈ C
0
. (11)
Dado x
k
∈ C
0
, defina T
k
: R
n
⇒ R
n
por T
k
(·) := T(·) + λ
k
∂
x
D
h
(·, x
k
) e encontre
x
k+1
∈ C
0
tal que
0 ∈ T
k
(x
k+1
). (12)
Sumário 3
Equivalentemente,
x
k+1
∈ [∂
x
D
h
(·, x
k
) +
1
λ
k
T]
−1
(x
k
), (13)
e ainda pela Proposição 1.6 (ii)
λ
k
[∇h(x
k
) − ∇h(x
k+1
)] ∈ T (x
k+1
). (14)
Mostraremos que a sequência gerada por (11) − (14) converge para a solução do problema
(6), isto é, para a solução do VIP(T, C).
Capítulo 1
Noções Preliminares
1.1 Existência de Soluções
Sejam dados um conjunto D ⊂ R
n
e uma função f : D → R. O problema de achar um
minimizador de f no conjunto D é escrito como
minf(x) sujeito a x ∈ D. (1.1)
O conjunto D é chamado de conjunto viável, os pontos de D são chamados de pontos
viáveis e f será chamada função objetivo.
Definição 1.1. Dizemos que um ponto x
∗
∈ D é
(i) minimizador global de (1.1), se
f(x
∗
) f(x) ∀ x ∈ D. (1.2)
(ii) minimizador local de (1.1) se existe uma vizihança V de x
∗
tal que
f(x
∗
) f(x) ∀ x ∈ D ∩ V. (1.3)
Se para todo x = x
∗
a desigualdade (1.2) ou (1.3) é estrita, dizemos que x
∗
será chamado
minimizador estrito (global ou local respectivamente).
Para D = R
n
o problema (1.1) toma a seguinte forma:
minf(x) sujeito a x ∈ R
n
, (1.4)
dizemos que o problema(1.4) é irrestrito.
4
Capítulo 1. Noções Preliminares 5
Teorema 1.1. (Teorema de Weierstrass) Sejam D um conjunto compacto não vazio e
f : D → R uma função contínua.
Então, o problema de minimizar f em D tem uma solução global.
Demonstração. Ver [10].
Definição 1.2. Dizemos que uma função f : D → R é coerciva no conjunto D quando
para toda sequência {x
k
} ⊂ D e ||x
k
|| → ∞ ou x
k
→ x ∈ D, quando k → ∞, tem-se
lim sup
k→∞
f(x
k
) = ∞.
Exemplo 1.1. Seja x
0
∈ R
n
, suponha que o problema (1.4) tem solução e defina a função
F : R
n
→ R por
F(x) := f(x) +
1
2
x − x
0
2
.
Então F é coerciva em R
n
.
De fato, considere h(x) =
1
2
x − x
0
2
, ∀ x ∈ R
n
, então F(x) = f(x) + h(x), ∀ x ∈ R
n
.
Como f é limitada inferiormente existe β ∈ R tal que f(x) β, ∀ x ∈ R
n
. Seja {x
k
}
k∈N
uma sequência em R
n
tal que lim
k→+∞
x
k
= +∞.
Assim, lim
k→+∞
h(x
k
) = lim
k→+∞
1
2
x
k
− x
0
2
= +∞.
Daí,
+∞= lim
k→+∞
[β + h(x
k
)] lim
k→+∞
[f(x
k
) + h(x
k
)] = lim
k→+∞
F(x
k
).
Portanto, lim
k→+∞
supF(x
k
) = +∞, logo F é coerciva em R
n
.
Proposição 1.1. Sejam D ⊂ R
n
e f : D → R uma função contínua coerciva em D.
Então, o problema de minimizar f em D possui uma solução global.
Demonstração. Ver [10].
Definição 1.3. Dizemos que a função f : D → R é semicontínua inferiormente no ponto
x ∈ D ⊂ R
n
, quando para qualquer seqência {x
k
} ⊂ R
n
tal que {x
k
} → x quando (k → ∞),
tem-se
lim inf
k→∞
f(x
k
) f(x).
Dizemos que f é semicontínua superiormente quando, nas mesmas condições,
lim sup
k→∞
f(x
k
) f(x).
A função f é semicontínua inferiormente (superiormente) no conjunto D, quando ela
semicontínua inferiormente (superiormente) em todos os pontos de D.
Capítulo 1. Noções Preliminares 6
1.2 Conjuntos Convexos
Um conjunto convexo é caracterizado por conter todos os segmento de retas cujos extremos
pertencem ao conjunto. Precisamente:
Definição 1.4. Um conjunto D ⊂ R
n
é convexo se para quaisquer x, y ∈ D e α ∈ [0, 1],
tem-se
αx + (1 − α)y ∈ D. (1.5)
O ponto αx + (1 − α)y, onde α ∈ [0, 1], se chama a combinação convexa de x e y (
com parâmetro α).
Exemplo 1.2. O conjunto vazio, o conjunto unitário e o próprio R
n
são exemplos triviais
de conjuntos convexos.
Exemplo 1.3. Um hiperplano do R
n
é um conjunto da forma H = {x ∈ R
n
|a, x = c},
onde a ∈ R
n
e c ∈ R. Segue da Definição 1.4 que H é um conjunto convexo.
Exemplo 1.4. Um semi-plano em R
n
é um conjunto da forma {x ∈ R
n
|a, x c}, onde
a ∈ R
n
e c ∈ R. Segue da Definição 1.4 que todo semi-plano é um conjunto convexo.
Definição 1.5. Dado x
i
∈ R
n
, α
i
∈ [0, 1], i = 1, ..., p, tais que
p
i=1
α
i
= 1, o ponto
p
i=1
α
i
x
i
chama-se a combinação convexa de pontos x
i
∈ R
n
com parâmetros α
i
, i =
1, ..., p.
Teorema 1.2. Um conjunto D ⊂ R
n
é convexo se, e somente se, para quaisquer p ∈ N,
x
i
∈ D e α
i
∈ [0, 1], i = 1, ..., p, tais que
p
i=1
α
i
= 1, a combinação convexa
p
i=1
α
i
x
i
pertence a D.
Demonstração. (⇒) Suponha que D ⊂ R
n
seja convexo. A prova é feita por indução
sobre p ∈ N.
Dados p ∈ N, x
i
∈ D e α
i
∈ [0, 1] tais que
p
i=1
α
i
= 1. Defina x =
p
i=1
α
i
x
i
.
i) Se p = 1 tem-se que α
1
= 1 e x = 1.x
1
∈ D.
ii) Suponha agora que vale para p = n. Mostraremos que vale para p = n + 1.
De fato, temos
n+1
i=1
α
i
= 1, então 1 −
n
i=1
α
i
= α
n+1
.
Se α
n+1
= 1, temos que α
i
= 0, ∀i = 1, ..., n.
Capítulo 1. Noções Preliminares 7
Logo, x =
p
i=1
0.x
i
+ 1.x
n+1
= x
n+1
∈ D.
Se α
n+1
∈ [0, 1), temos, (1 − α
n+1
) > 0. Logo,
x =
n+1
i=1
α
i
x
i
=
n
i=1
α
i
x
i
+ α
n+1
x
n+1
= (1 − α
n+1
)
n
i=1
α
i
(1 − α
n+1
)
x
i
+ α
n+1
x
n+1
. (1.6)
Tome y =
n
i=1
β
i
x
i
, onde β
i
=
α
i
1 − α
n+1
, i = 1, ..., n.
Como
n+1
i=1
α
i
= 1, tem-se 1 − α
n+1
=
n
i=1
α
i
, então
n
i=1
β
i
=
1
1 − α
n+1
n
i=1
α
i
=
1
1 − α
n+1
(1 − α
n+1
) = 1.
Portanto, por hipótese de indução y ∈ D.
Daí, substituindo y em (1.6), obtemos
x = (1 − α
n+1
)y + α
n+1
x
n+1
.
Segue da convexidade de D que x =
n+1
i=1
α
i
x
i
∈ D. Logo, x =
p
i=1
α
i
x
i
∈ D,
∀p ∈ N, com x
i
∈ D α
i
∈ [0, 1] tais que
p
i=1
α
i
= 1.
(⇐) Suponha que
p
i=1
α
i
x
i
∈ D, ∀p ∈ N com x
i
∈ D e α
i
∈ [0, 1] tais que
p
i=1
α
i
= 1.
Então, para p = 2, temos que
2
i=1
α
i
x
i
= α
1
x
1
+α
2
x
2
∈ D, com x
1
, x
2
∈ D e α
1
, α
2
∈ [0, 1],
tal que α
1
+ α
2
= 1. Assim, α
1
= 1 − α
2
, logo (1 − α
2
)x
1
+ α
2
x
2
= α
1
x
1
+ α
2
x
2
∈ D.
Portanto, pela Definição 1.4, D é um conjunto convexo.
1.3 Funções Convexas
Nesta seção estudaremos a definição e algumas caracterizações de funções convexas, que
serão de grande importância para estudarmos as seções seguintes e os próximos capítulos.
Definição 1.6. Se D ⊂ R
n
é um conjunto convexo, diz-se que f : D → R é convexa em
D quando para quaisquer x, y ∈ D e α ∈ [0, 1], tem-se
f(αx + (1 − α)y) αf(x) + (1 − α)f(y). (1.7)
Capítulo 1. Noções Preliminares 8
Diz-se que f estritamente convexa quando a desigualdade acima é estrita para todo x = y
e α ∈ (0, 1).
Exemplo 1.5. A função f : R
n
→ R dada por f(x) = x − x
0
2
para x
0
∈ R
n
é
estritamente convexa.
Proposição 1.2. Seja D ⊂ R
n
um conjunto convexo. Se f : D → R é uma função
convexa e h : D → R é estritamente convexa, então f + g é estritamente convexa.
Demonstração. Sejam x, y ∈ D, então
f(αx + (1 − α)y) αf(x) + (1 − α)f(y), para α ∈ [0, 1] (1.8)
e
h(αx + (1 − α)y) < αh(x) + (1 − α)h(y), para α ∈ (0, 1) (1.9)
e x = y. Portanto, por (1.8) e (1.9), tem-se
(f + h)(αx + (1 − α)y) = f(αx + (1 − α)y) + h(αx + (1 − α)y)
αf(x) + (1 − α)f(y) + h(αx + (1 − α)y)
< αf(x) + (1 − α)f(y) + αh(x) + (1 − α)h(y)
= α(f + h)(x) + (1 − α)(f + h)(y).
Logo, f + h é estritamente convexa.
Definição 1.7. O epígrafo da função f : D → R é o conjunto
E
f
= {(x, c) ∈ D × R | f(x) c}.
A relação entre convexidade de conjuntos e de funções é dada pelo seguinte teorema.
Teorema 1.3. Seja D ⊂ R
n
um conjunto convexo. Uma função f : D → R é convexa
em D se, e somente se, o epígrafo de f é um conjunto convexo em R
n
× R.
Demonstração. (⇒) Suponha que f : D → R é convexa em D. Sejam (x, c
1
) ∈ E
f
e
(y, c
2
) ∈ E
f
. Então,
f(x) c
1
e f(y) c
2
.
Pela convexidade de f, para α ∈ [0, 1], segue que
f(αx + (1 − α)y) αf(x) + (1 − α)f(y) αc
1
+ (1 − α)c
2
.
Capítulo 1. Noções Preliminares 9
Daí, pela Definição 1.7 , (αx + (1 − α)y, αc
1
+ (1 − α)c
2
) ∈ E
f
.
Portanto, α(x, c
1
) + (1 − α)(y, c
2
) ∈ E
f
. Logo, E
f
é um conjunto convexo.
(⇐) Suponha agora que E
f
é um conjunto convexo em R
n
× R. Sejam x, y ∈ D. Tem-se
que (x, f(x)) ∈ E
f
, pois f(x) f(x). De forma análoga, (y, f(y)) ∈ E
f
.
Pela convexidade de E
f
em R
n
× R, α(x, f(x)) + (1 − α)(y, f(y)) ∈ E
f
, α ∈ [0, 1]. Daí
(αx + (1 − α)y, αf(x) + (1 − α)f(y)) ∈ E
f
. Pela Definição 1.7,
f(αx + (1 − α)y) αf(x) + (1 − α)f(y).
Portanto, f é uma função convexa em D.
Dizemos que
minf(x) sujeito a x ∈ D (1.10)
é um problema de minimização convexa quando D ⊂ R
n
é um conjunto convexo e
f : D → R é uma função convexa no conjunto D. A importância da convexidade já pode
ser vista no resultado seguinte.
Teorema 1.4. Sejam D ⊂ R
n
um conjunto convexo e f : D → R uma função convexa
em D. Então todo minimizador local do problema (1.10) é global.
Além disso, o conjunto de minimizadores é convexo. Se f é estritamente convexa, não
pode haver mais de um minimizador.
Demonstração. Ver [10].
Definição 1.8. Seja D ⊂ R
n
. O conjunto de nível da função f : D → R associado a
c ∈ R, é o conjunto dado por
L
f,D
(c) = {x ∈ D|f(x) c}.
Quando uma função é diferenciável, a convexidade admite caracterizações que são
muito úteis para determinar se uma função é convexa ou não.
Teorema 1.5. (Caracterizações de funções convexas diferenciáveis)
Sejam D ⊂ R
n
um conjunto convexo e aberto e f : D → R uma função diferenciável em
D. Então as propriedades seguintes são equivalentes:
Capítulo 1. Noções Preliminares 10
1) A função f é convexa em D.
2) Para todo x ∈ D e todo y ∈ D,
f(y) f(x) + ∇f(x), y − x.
3)Para todo x ∈ D e todo y ∈ D,
∇f(y) − ∇f(x), y − x 0.
Demonstração. 1) ⇒ 2) Suponha que f seja convexa, então para x, y ∈ D e α ∈ (0, 1],
tem-se que
f(αy + (1 − α)x) αf(y) + (1 − α)f(x).
Considere d = y − x. Assim, x + αd = x + α(y − x) = (1 − α)x + αy. Com isso temos
que f(x + αd) αf(y) + (1 − α)f(x). Então,
α[f(y) − f(x)] f(x + αd) − f(x).
Isto implica que
f(y) − f(x)
f(x + αd) − f(x)
α
,
pois α > 0.
Daí, passando ao limite quando α → 0
+
, obtemos
f(y) − f(x) lim
α→0
+
f(x + αd) − f(x)
α
=
∂f
∂d
(x) = ∇f(x), d = ∇f(x), y − x.
Portanto, para todo x, y ∈ D
f(y) f(x) + ∇f(x), y − x. (1.11)
2) ⇒ 3) Trocando x por y em (1.11), obtemos
f(x) f(y) + ∇f(y), x − y (1.12)
Somando (1.11) e (1.12), tem-se
∇f(x), y − x + ∇f(y), x − y 0
∇f(x), y − x − ∇f(y), y − x 0
∇f(x) − ∇f(y), y − x 0
∇f(y) − ∇f(x), y − x 0, ∀x, y ∈ D.
Capítulo 1. Noções Preliminares 11
3) ⇒ 2) Suponha que 3) seja verdadeiro. Sejam x, y ∈ D. Pelo teorema do valor médio
(ver [11]), existe α ∈ (0, 1) tal que
f(y) − f(x) =
∂f
∂d
(x + αd) = ∇f(x + αd), d (1.13)
onde d = x − y.
Aplicando 3) para x + αd e x, obtemos
0 ∇f(x + αd) − ∇f(x), x + αd − x = ∇f(x + αd) − ∇f(x), αd.
Então
∇f(x + αd), αd ∇f(x), αd ⇒ ∇f(x + αd), d ∇f(x)d. (1.14)
Combinando (1.13) e (1.14) e usando d = y − x, obtemos
f(y) − f(x) ∇f(x), d ⇒ f(y) − f(x) ∇f(x), y − x.
Portanto, para todo x, y ∈ D
f(y) f(x) + ∇f(x), y − x.
2) ⇒ 1) Suponha agora que 2) seja verdadeiro. Aplicando 2) para x e x + αd, com
d = y − x, segue que
f(x) f(x + αd) + ∇f(x + αd), x − (x + αd) = f(x + αd) + ∇f(x + αd), −αd.
Portanto,
f(x) f(x + αd) − α∇f(x + αd), d.
Daí,
(1 − α)f(x) (1 − α)f(x + αd) − (1 − α)α∇f(x + αd), d. (1.15)
Analogamente, aplicando 2) para y e x + αd, obtemos
αf(y) αf(x + αd) + α(1 − α)∇f(x + αd), d. (1.16)
Somando (1.15) e (1.16), tem-se
(1 − α)f(x) + αf(y) (1 − α)f(x + αd) + αf(x + αd) = f(x + αd). (1.17)
Subtituindo d = y − x em (1.17), temos
(1 − α)f(x) + αf(y) f(x + α(y − x)) = f(x + αy − αx) = f((1 − α)x + αy).
Portanto, f é convexa em D.
Capítulo 1. Noções Preliminares 12
Corolário 1.3.1. Sejam D ⊂ R
n
um conjunto convexo e aberto e f : D → R uma função
diferenciável em D. Então as propriedades seguintes são equivalentes:
1) A função f é estritamente convexa em D.
2) Para todo x ∈ D e todo y ∈ D tal que x = y,
f(y) > f(x) + ∇f(x), y − x.
3) Para todo x ∈ D e todo y ∈ D tal que x = y,
∇f(y) − ∇f(x), y − x > 0.
Demonstração. Segue da Definição 1.6 e do Teorema 1.5
Teorema 1.6. Sejam f : R
n
→ R uma função diferenciável e
¯
x minimizador local de f.
Então ∇f(
¯
x) = 0.
Demonstração. Seja d ∈ R
n
arbitrário, porém fixo. Como
¯
x é mínimo de f, existe ε > 0
tal que
f(
¯
x) f(
¯
x + td), ∀t ∈ [0, ε]. (1.18)
Da diferenciabilidade de f, tem-se
f(
¯
x + td) − f(
¯
x) = ∇f(
¯
x), td + r(t), com lim
t→0
+
r(t)
t
= 0. (1.19)
Daí, usando (1.18) em (1.19), obtemos
t∇f(
¯
x), d + r(t) 0. (1.20)
Dividindo (1.20) por t > 0, tem-se
∇f(
¯
x), d +
r(t)
t
0, (1.21)
e tomando o limite em (1.21) quando t → 0
+
, obtemos
∇f(
¯
x), d 0. (1.22)
Como d ∈ R
n
é arbitrário, podemos escolher d = −∇f(
¯
x) e substituindo em (1.22),
tem-se
∇f(
¯
x), −∇f(
¯
x) 0.
Portanto,
∇f(
¯
x), ∇f(
¯
x) 0.
Logo, ∇f(
¯
x) = 0.
Capítulo 1. Noções Preliminares 13
1.4 Subgradiente de uma Função
A seguinte noção é fundamental em Análise Convexa.
Definição 1.9. Seja f : R
n
→ R uma função convexa. Dizemos que y ∈ R
n
é um
subgradiente de f no ponto x ∈ R
n
se
f(z) f(x) + y, z − x ∀z ∈ R
n
.
O conjunto de todos os subgradientes de f em x, é chamado o Subdiferencial de f em
x; e denotado por ∂f(x). Isto é,
∂f(x) := {y ∈ R
n
| f(z) f(x) + y, z − x}.
Observação 1.1. Considerando z ∈ R
n
como z = x + αd, onde d ∈ R
n
e α > 0.
Seja s ∈ ∂f(x), pela Definição 1.9, tem-se
s ∈ ∂f(x) ⇔ f(z) − f(x) s, z − x, ∀ z ∈ R
n
⇔ f(x + αd) − f(x) s, x + αd − x
⇔ f(x + αd) − f(x) s, αd
⇔
f(x + αd) − f(x)
α
s, d.
Então,
lim
α→0+
f(x + αd) − f(x)
α
s, d.
Portanto,
∂f
∂d
(x) s, d, ∀ d ∈ R
n
.
Assim, temos que a Definição 1.9 é equivalente a seguinte definição
∂f(x) := {y ∈ R
n
|
∂f
∂d
(x) y, d, ∀ d ∈ R
n
}.
Notação:
∂f
∂d
(x) = f
(x, d).
Teorema 1.7. Seja f : R
n
→ R uma função convexa. Então para todo x ∈ R
n
, o conjunto
∂f(x) é convexo, compacto e não vazio.
Demonstração. Ver [10].
Proposição 1.3. Seja f : R
n
→ R uma função convexa. Então, para todo d ∈ R
n
, temos
∂f
∂d
(x) = max
s∈∂f(x)
s, d.
Capítulo 1. Noções Preliminares 14
Demonstração. Ver [10].
Proposição 1.4. Uma função convexa f : R
n
→ R é diferenciável se, e somente se, o
conjunto ∂f(x) contém um só elemento. Neste caso, ∂f(x) = {∇f(x)}.
Demonstração. (⇒) Suponha que f seja diferenciável em x ∈ R
n
. Então, sendo f convexa,
tem-se pelo Teorema 1.5 que f(z) f(x) + ∇f(x), z − x, z ∈ R
n
. Assim, pela
Definição 1.9 ∇f(x) ∈ ∂f(x). Seja s ∈ ∂f(x). Logo, f(z) f(x) + s, z − x, z ∈ R
n
.
Considere λd = z − x, com λ > 0. Então,
f(x + λd) f(x) + s, λd. (1.23)
Como f é diferenciável em x,
f(x + λd) = f(x) + ∇f(x), λd + λdr(λd), com lim
λ→0
r(λd) = 0. (1.24)
Então, juntando (1.23) e (1.24), obtemos
s, λd ∇f(x), λd + λdr(λd)
s, d ∇f(x), d + dr(λd) (1.25)
Passando ao limite em (1.25) quando λ → 0, obtemos
s, d ∇f(x), d + d lim
λ→0
r(λd) = ∇f(x), d.
Então,
s − ∇f(x), d 0, ∀d ∈ R
n
. (1.26)
Assim, tomando d = s − ∇f(x) em (1.26), obtemos
s − ∇f(x), s − ∇f(x) 0.Logo, s = ∇f(x).
Portanto, ∂f(x) = {∇f(x)}.
(⇐) Reciprocamente suponha que ∂f(x) = {s}. Pela Proposição 1.3,
∂f
∂d
(x) = s, d
∀d ∈ R
n
. Escolhendo d como os elementos da base canônica de R
n
, tem-se que
s
i
=
∂f
∂x
i
(x), i = 1, ..., n. Assim,
∂f
∂d
(x) = ∇f(x), d, ∀ d ∈ R
n
.
Portanto, f é diferenciável em x.
Teorema 1.8. Seja f : R
n
→ R um função convexa. O ponto
¯
x ∈ R
n
é mínimo de f se,
e somente se, 0 ∈ ∂f(
¯
x).
Capítulo 1. Noções Preliminares 15
Demonstração. (⇒) Suponha que
¯
x ∈ R
n
seja mínimo de f. Então
f(
¯
x) f(x), ∀x ∈ R
n
.
Daí,
f(x) f(
¯
x) + 0, x −
¯
x, ∀ x ∈ R
n
.
Portanto, pela Definição 1.9, 0 ∈ ∂f(
¯
x).
(⇐) Reciprocamente, se 0 ∈ ∂f(
¯
x), pela Definição 1.9,
f(x) f(
¯
x) + 0, x −
¯
x = f(
¯
x), ∀ x ∈ R
n
.
Logo, f(x) f(
¯
x) ∀ x ∈ R
n
. Portanto,
¯
x é mínimo de f.
Exemplo 1.6. Seja f(x) = |x| para todo x ∈ R. Note que f é uma função convexa.
Encontremos o seu subdiferencial que é dado pela definição por:
∂f(x) = {s ∈ R; s(y − x) |y| − |x|, ∀ y ∈ R} . Então,
i) Se x > 0, tem-se que f é diferenciável, portanto ∂f(x) = {1}, que é o gradiente de f.
ii) Se x < 0, f é diferenciável, assim ∂f(x) = {1}, que é o gradiente de f.
iii) Se x = 0, tem-se f(x) = 0, daí para todo y ∈ R, obtemos |y| sy então, se y 0,
s 1 e se y < 0, implica s −1.
Portanto, ∂f(x) = [−1, 1].
Logo, por i),ii) e iii),
∂f(x) =
{1}, se x > 0
[−1, 1], se x = 0
{−1}, se x < 0
.
1.5 Funções Convexas com valores em R ∪ {+∞}
Nesta seção trataremos de estender as funções convexas definidas na seção 1.3.
Definição 1.10. Uma função f : R
n
→ R ∪ {+∞}, não identicamente +∞ é dita convexa
quando, para todo (x, y) ∈ R
n
× R
n
e todo α ∈ (0, 1), tem-se
f(αx + (1 − α)y) αf(x) + (1 − α)f(y),
como uma desigualdade em R ∪ {+∞}.
Capítulo 1. Noções Preliminares 16
Podemos observar que de acordo com a Definição 1.6, para D ⊂ R
n
um conjunto
convexo, não vazio e f : D → R uma função convexa, podemos estender a função f a uma
função convexa como na Definição 1.10 da seguinte forma
¯
f : R
n
→ R ∪ {+∞},
¯
f(x) =
f(x), se x ∈ D
+∞, se x ∈ D
Então, obtemos uma função
¯
f, a qual chamamos de função convexa própria.
Definição 1.11. O domínio efetivo de uma função convexa f : R
n
→ R ∪ {+∞} é o
conjunto denotado por dom(f) = {x ∈ R
n
; f(x) < +∞}.
Definição 1.12. Uma função f : R
n
→ R ∪{+∞} é chamada fechada quando seu epígrafo
é fechado em R
n
× R ou equivalentemente se seus conjuntos de nível são fechados.
Definição 1.13. Seja f : R
n
→ R ∪ {+∞} uma função convexa. O subdiferencial de f em
x ∈ R
n
é o conjunto ∂f(x) definido por
∂f(x) =
{s ∈ R
n
; f(y) f(x) + s, y − x, ∀ y ∈ R
n
}, se x ∈ dom(f)
∅, se x ∈ dom(f)
Exemplo 1.7. Seja C ⊂ R
n
fechado e convexo. A função δ
C
: R
n
→ R ∪ {+∞} definida
por:
δ
C
(x) =
0, se x ∈ C
+∞, se x ∈ C
é chamada a função indicadora de C.
A qual é convexa se, e somente se, C é um conjunto convexo.
De fato, se x ∈ C tem-se δ
C
= +∞. Assim, para todo d ∈ R, d < +∞ = δ
C
(x). Logo,
(x, d) ∈ E
δ
C
.
Se x ∈ C, tem-se δ
C
(x) = 0. Então, δ
C
(x) d, ∀ d ∈ [0, +∞).
Portanto, (x, d) ∈ E
δ
C
. Logo, E
δ
C
= C × [0, +∞).
Daí, se δ
C
é convexa temos que E
δ
C
é convexo, portanto C × [0, +∞) é convexo. Logo, C
é convexo.
Reciprocamente, se C é convexo, temos que E
δ
C
é convexo. Logo, δ
C
é convexa.
Agora vamos calcular o subdiferencial da função indicadora.
Seja s ∈ ∂δ
C
(x), então.
i)Se x ∈ C, tem-se δ
C
(x) = +∞, daí
δ
C
(y) +∞, ∀ y ∈ R
n
.
Capítulo 1. Noções Preliminares 17
Que é um absurdo. Logo, ∂δ
C
(x) = ∅.
ii) Se x ∈ C, tem-se δ
C
(x) = 0, então
δ
C
(y) s, y − x, ∀ y ∈ R
n
.
Daí, considere os dois casos.
1) Se y ∈ C, obtemos
s, y − x +∞.
2) Se y ∈ C, tem-se δ
C
(y) = 0, assim
s, y − x 0.
Portanto, por 1) e 2), obtemos
∂δ
C
(x) = {s ∈ R
n
; s, y − x 0, ∀ y ∈ C}.
Logo,
∂δ
C
(x) =
{s ∈ R
n
; s, y − x 0, ∀ y ∈ C}, se x ∈ C
∅, se x ∈ C
Teorema 1.9. Sejam f, g : R
n
→ R ∪ {+∞} funções convexas.
i)Tem-se ∂(f + g)(x) ⊃ ∂f(x) + ∂g(x), para x ∈ R
n
.
ii) Seja x ∈ ri(dom(f)) ∩ ri(dom(g)) tal que ∂f(x) e ∂g(x) sejam não vazios. Então,
∂(f + g)(x) = ∂f(x) + ∂g(x).
Demonstração. i) Se s ∈ ∂f(x), z ∈ ∂g(x), então s + z ∈ ∂f(x) + ∂g(x).
Daí, para todo y ∈ R
n
f(y) f(x) + s, y − x e g(y) g(x) + z, y − x.
Portanto,
(f + g)(y) (f + g)(x) + s + z, y − x.
Segue que, s + z ∈ ∂(f + g)(x). Logo, ∂(f + g)(x) ⊃ ∂f(x) + ∂g(x).
ii) Suponha que ∂(f + g)(x) ⊂ (∂f(x) + ∂g(x)), isto é, existe ω ∈ ∂(f + g)(x), tal que
ω ∈ (∂f(x) + ∂g(x)). Pela compacidade de ∂f(x) + ∂g(x) e pelo Teorema da Separação
Estrita existem a ∈ R
n
e c ∈ R tal que
a, s + z < c < a, ω (f + g)
(x, a) = f
(x, a) + g
(x, a), ∀ s ∈ ∂f(x), ∀ z ∈ ∂g(x),
Capítulo 1. Noções Preliminares 18
que é um absurdo pois, pela Proposição 1.3, existe um s
0
+ z
0
∈ (∂f(x) + ∂g(x)) tal que
a, s
0
= f
(x, a) e a, z
0
= g
(x, a).
Portanto, ∂(f + g)(x) = ∂f(x) + ∂g(x).
1.6 Função Conjugada de uma Função Convexa
Para demonstrar que o subdiferencial de uma função convexa é um operador monótono
maximal precisaremos da definição de função conjugada de uma função convexa e de
alguns resultados.
Definição 1.14. Seja f : R
n
→ R ∪ {+∞} uma função convexa própria. A função
f
∗
: R
n
→ R ∪ {+∞} definida por
f
∗
(s) = sup
x∈R
n
{x, s − f(x)},
para todo s ∈ R
n
, é chamada a função conjugada da função f.
Exemplo 1.8. Considere a função convexa f(x) = |x| para todo x ∈ R, encontremos sua
função conjugada.
Pela definição de conjugada, para todo s ∈ R
n
, f
∗
(s) = sup
x∈R
n
{x, s − f(x)}. Portanto,
f
∗
(s) = sup
x∈R
n
{(s − 1)x}, se x 0 e f
∗
(s) = sup
x∈R
n
{(s + 1)x}, se x < 0. Logo,
f
∗
(s) =
+∞, se s > 1
0, se s 1
.
Observação 1.2. Seja f : R
n
→ R ∪ {+∞}. Segue da Definição 1.14 que para cada
x ∈ R
n
e cada s ∈ R
n
, tem-se f
∗
(s) x, s − f(x), isto é,
f
∗
(s) + f(x) x, s (1.27)
sempre que o lado esquerdo da desigualdade (1.27) estiver definido. A relação (1.27) é
chamada a desigualdade de Fenchel.
Teorema 1.10. Seja f : R
n
→ R ∪ {+∞} uma função convexa própria semicontínua
inferiormente , onde f é finita em x ∈ R
n
. Então, s ∈ ∂f(x) se, e somente se, f
∗
(s) =
x, s − f(x).
Capítulo 1. Noções Preliminares 19
Demonstração. (⇒) Seja s ∈ ∂f(x). Então
s, z − x f(z) − f(x)
isto é,
s, z − f(z) s, x − f(x),
para todo z ∈ R
n
.
Portanto,
f
∗
(s) = sup
z∈R
n
{s, z − f(z)} s, x − f(x).
Logo, f
∗
(s) = s, x − f(x).
(⇐) Se f
∗
(s) = sup
z∈R
n
{s, z − f(z)} = s, x − f(x), tem-se f
∗
(s) < +∞. Assim,
s, z − f(z) s, x − f(x).
Portanto,
s, z − x f(z) − f(x), ∀z ∈ R
n
.
Logo, s ∈ ∂f(x).
Este teorema garante que se f : R
n
→ R é uma função convexa e s ∈ ∂f(x) para algum
x ∈ R
n
, então f
∗
(x) < +∞.
Teorema 1.11. Seja f : R
n
→ R ∪ {+∞} uma função convexa própria semicontínua
inferiormente e x ∈ R
n
. Então, a função conjugada f
∗
: R
n
→ R ∪ {+∞} é uma função
convexa.
Demonstração. Dados s
1
, s
2
∈ R
n
. Faremos a prova em dois casos:
i) Se s
1
, s
2
∈ R
n
, tais que f
∗
(s
1
) < +∞ e f
∗
(s
2
) < +∞. Então para t ∈ [0, 1], tem-se,
f
∗
((1 − t)s
1
+ ts
2
) = sup
x∈R
n
{x, (1 − t)s
1
+ ts
2
− f(x)}. (1.28)
Daí, somando e subtraindo tf(x) a (1.28) obtemos
f
∗
((1 − t)s
1
+ ts
2
) = sup
x∈R
n
{x, (1 − t)s
1
+ ts
2
− f(x) + tf(x) − tf(x)}.
Assim,
f
∗
((1 − t)s
1
+ ts
2
) = sup
x∈R
n
{(1 − t)[x, s
1
− f(x)] + t[x, s
2
− f(x)]}.
Capítulo 1. Noções Preliminares 20
Segue que,
f
∗
((1 − t)s
1
+ ts
2
) (1 − t) sup
x∈R
n
{x, s
1
− f(x)} + t sup
x∈R
n
{x, s
2
− f(x)}.
Poratnto, pela Definição1.14
f
∗
((1 − t)s
1
+ ts
2
) (1 − t)f
∗
(s
1
) + tf
∗
(s
2
).
Logo, f
∗
é uma função convexa.
ii) Se para s
1
, s
2
∈ R
n
, f
∗
(s
1
) = +∞ ou f
∗
(s
2
) = +∞, então temos trivialmente que
f
∗
((1 − t)s
1
+ ts
2
) (1 − t)f
∗
(s
1
) + tf
∗
(s
2
).
Portanto, f
∗
é uma função convexa.
Definição 1.15. Seja f : R
n
→ R ∪ {+∞} uma função convexa. Dizemos que a função
f
∗∗
: R
n
→ R ∪ {+∞} é a função conjugada (f
∗
)
∗
da conjugada de f.
Lema 1.6.1. Seja f : R
n
→ R ∪ {+∞} uma função convexa. Então f
∗∗
é o supremo do
conjunto de todas as funções afins que minoram f.
Demonstração. Seja A o conjunto de todas as funções afins que minoram f. Considere
µ = sup{g; g ∈ A}, provaremos que µ = f
∗∗
.
De fato, para cada s ∈ R
n
, a função g(x) = x, s − f
∗
(s) é uma função afim. Pela
desigualdade de Fenchel,
f(x) + f
∗
(s) x, s x ∈ R
n
.
Segue que,
g(x) = x, s − f
∗
(s) f(x) + f
∗
(s) − f
∗
(s) = f(x).
Assim, g é uma minorante de f. Então, g ∈ A.
Portanto,
f
∗∗
(x) = sup
s∈R
n
{x, s − f
∗
(s)} sup
x∈R
n
g(x) = µ(x).
Logo,
f
∗∗
(x) µ(x), ∀ x ∈ R
n
. (1.29)
Agora, se h ∈ A, então h é da forma h(x) = x, s − α, onde s ∈ R
n
e α ∈ R, que implica
que, para todo x ∈ R
n
, tem-se x, s − α f(x).
Isto é,
x, s − f(x) α.
Capítulo 1. Noções Preliminares 21
Então,
f
∗
(s) = sup
x∈R
n
{x, s − f(x)} α.
Assim,
−α −f
∗
(s).
Segue que,
h(x) = x, s − α x, s − f
∗
(s).
Portanto, para cada x ∈ R
n
µ(x) = sup
x∈R
n
h(x) sup
s∈R
n
{x, s − f
∗
(s)} = f
∗∗
(x).
Logo,
µ(x) f
∗∗
(x), ∀ x ∈ R
n
. (1.30)
De (1.29) e (1.30), obtemos µ = f
∗∗
.
Proposição 1.5. Seja f : R
n
→ R ∪ {+∞} uma função convexa própria semicontínua
inferiormente. Então f = f
∗∗
.
Demonstração. i)Mostraremos que f
∗∗
f. De fato, por definição
f
∗∗
(ω) := sup
y∈R
n
{ω, y − f
∗
(y)}. (1.31)
Por outro lado,
f
∗
(y) = sup
ω∈R
n
{y, ω − f(ω)} y, ω − f(ω),
para todo ω ∈ R
n
. Segue que,
y, ω − f
∗
(y)} f(ω), ∀ ω ∈ R
n
. (1.32)
Portanto, de (1.31) e (1.32), tem-se f
∗∗
(ω) f(ω), ∀ ω ∈ R
n
.
ii) Mostraremos que f f
∗∗
. Suponha que não ocorra f f
∗∗
, isto é, existe ω
0
∈ R
n
tal
que f
∗∗
(ω
0
) < f(ω
0
). Assim, existe α ∈ R tal que
f
∗∗
(ω
0
) < α < f(ω
0
). (1.33)
Da convexidade de f, existe uma função afim h minorando f dada por
h(x) = α − s, x − ω
0
, onde h(ω
0
) = α.
Capítulo 1. Noções Preliminares 22
Como h < f, temos pelo Lema 1.6.1 que h(x) f
∗∗
(x), em particular para x = ω
0
, tem-se
h(ω
0
) f
∗∗
(ω
0
) que implica α f
∗∗
(ω
0
), contrariando (1.33).
Portanto, f < f
∗∗
.
Logo, de i) e ii), obtemos f = f
∗∗
.
1.7 Funções e Distâncias de Bregman
Seja S ⊂ R
n
um conjunto aberto e convexo, e S o fecho de S. Considere a função h : S → R
convexa e diferenciável em S. Defina D
h
: S × S → R por
D
h
(x, y) = h(x) − h(y) − ∇h(y), x − y, (1.34)
induzida por h.
Definição 1.16. Dizemos que h é uma função de Bregman e D
h
a distância de Bregman
induzida por h se as seguintes condições são satisfeitas:
B
1
) h é continuamente diferenciável em S.
B
2
) h é estritamente convexa e contínua em S.
B
3
) Para todo δ > 0 os conjuntos Γ
1
(y, δ) = {x ∈ S; D
h
(x, y) δ} e
Γ
2
(x, δ) = {y ∈ S; D
h
(x, y) δ} são limitados para todo y ∈ S, e x ∈ S, respectivamente.
B
4
) Se a sequência {y
k
} ⊂ S, converge para y
∗
, então lim
k→∞
D
h
(y
∗
, y
k
) = 0.
B
5
) Se {x
k
} ⊂ S e {y
k
} ⊂ S são sequências tais que {x
k
} é limitada, lim
k→∞
y
k
= y
∗
e
lim
k→∞
D
h
(x
k
, y
k
) = 0, então lim
k→∞
x
k
= y
∗
.
Dizemos que uma função de Bregman h é coerciva na fronteira se satisfaz a seguinte
condição:
B
6
) Se {y
k
} ⊂ S é tal que lim
k→∞
y
k
= y ∈ ∂S, então
lim
k→∞
∇h(y
k
), y − y
k
= −∞, ∀ y ∈ S. (1.35)
Dizemos que h é zona coerciva se satisfaz a seguinte condição:
B
7
) Para todo y ∈ R
n
existe x ∈ S tal que ∇h(x) = y.
S é chamado de zona de h.
Vejamos agora alguns exemplos.
Observação 1.3. A definição de funções e distância de Bregman acima pode ser definida
de outra maneira (ver[19]), sendo suficiente considerar apenas (B
1
) − (B
4
), onde em (B
3
)
é utilizado apenas um dos conjuntos de níveis e (B
5
) segue de (B
1
) e (B
2
).
Capítulo 1. Noções Preliminares 23
Exemplo 1.9. Seja h : R
n
→ R, tal que h(x) = ||x||
2
. Neste caso D
h
(x, y) = ||x − y||
2
.
Exemplo 1.10. S = R
n
++
, h(x) =
n
i=1
x
i
log x
i
estendido com a continuidade até a
fronteira de R
n
++
com a convenção de que 0 log 0 = 0. Neste caso,
D
h
(x, y) =
n
i
(x
i
log
x
i
y
i
+ y
i
− x
i
),
que é Kulblback-Leibeler divergente, bastante usada em Estatística.
Observação 1.4. Podemos verificar facilmente que D
h
(x, y) 0 para todo x ∈ S, y ∈ S
e D
g
(x, y) = 0 se, e somente se, x = y.
Proposição 1.6. Se h é uma função de Bregman com zona S então:
i) D
h
(x, y) − D
h
(x, z) − D
h
(z, y) = ∇h(y) − ∇h(z), z − x, ∀x ∈ S, ∀y, z ∈ S.
ii) ∂
x
D
h
(x, y) = ∇h(x) − ∇h(y), ∀x, y ∈ S.
iii) D
h
(·, y) é estritamente convexa para todo y ∈ S.
Demonstração. i) De (1.34), para x ∈ S, y, z ∈ S, temos
D
h
(x, y) − D
h
(x, z) − D
h
(z, y) = h(x) − h(y) − ∇h(y), x − y
−h(x) + h(z) + ∇h(z), x − z
−h(z) + h(y) + ∇h(y), z − y
= ∇h(y), z − y + y − x + ∇h(z), x − z
= ∇h(y), z − x − ∇h(z), z − x
= ∇h(y) − ∇h(z), z − x.
ii) Sejam x, z ∈ S. Como D
h
(x, y) = h(x) − h(y) − ∇h(y), x − y então
∂
x
D
h
(x, y) = ∇h(x) − 0 −
∂
∂x
∇h(y), x − y
= ∇h(x) − ∇h(y).
iii) Para y ∈ S, defina
G : S −→ R
x −→ := D
h
(x, y).
Sejam x
1
, x
2
∈ S, com x
1
= x
2
. Pelo item (ii), ∇G(x
1
) = ∇h(x
1
) − ∇h(y) e
∇G(x
2
) = ∇h(x
2
) − ∇h(y). Logo,
∇G(x
1
) − ∇G(x
2
), x
1
− x
2
= ∇h(x
1
) − ∇h(y) − ∇h(x
2
) + ∇h(y), x
1
− x
2
= ∇h(x
1
) − ∇h(x
2
), x
1
− x
2
> 0,
Capítulo 1. Noções Preliminares 24
pois h é estritamente convexa em S. Portanto, G = D
h
(·, y) é estritamente covexa em S,
para cada y ∈ S.
A importância de distância de Begman pode ser vista em [18].
Capítulo 2
Operadores Monótonos
2.1 Operadores Monótonos e Monótonos Maximais
Nesta seção apresentaremos os principais resultados e definições de operadores monótonos.
Seja A : R
n
→ R
n
uma transformação linear, diz-se que A é semidefinida positiva se
x, Ax 0, para todo x ∈ R
n
.
Então para quaisquer x, y ∈ R
n
, tem-se
0 x − y, A(x − y) = x − y, Ax − Ay.
Um operador monótono é uma generalização de uma transformação linear semidefinida
positiva (não necessariamente linear).
Definição 2.1. Um operador T : R
n
→ R
n
(não necessariamente linear) diz-se monótono
se para todo x, y ∈ R
n
T(x) − T(y), x − y 0. (2.1)
Observação 2.1. T é chamado estritamente monótono quando a desigualdade (2.1) é
estrita para x = y.
Exemplo 2.1. Seja f : R
n
→ R uma função convexa (resp. estritamente convexa)
e diferenciável. Então ∇f : R
n
→ R
n
é um operador monótono (resp. estritamente
monótono). Segue do Teorema 1.5.
Como ∂f associa a cada vetor x ∈ R
n
, não exatamente a cada vetor de R
n
, mas a
um subconjunto do R
n
. Estenderemos a noção de operador monótono ponto a ponto a
operador ponto-conjunto. Notação: T : R
n
→ P(R
n
) ou T : R
n
⇒ R
n
.
25
Capítulo 2. Operadores Monótonos 26
Definição 2.2. Seja T : R
n
⇒ R
n
um operador.
i) O domínio de T é o conjunto dom(T ) = {x ∈ R
n
; T(x) = ∅}.
ii) A imagem de T é o conjunto
R(T) =
x∈dom(T )
T(x).
Definição 2.3. Dado T : R
n
⇒ R
n
, o operador T
−1
: R
n
⇒ R
n
é definido pela seguinte
relação
x ∈ T
−1
(y) ⇔ y ∈ T(x).
Definição 2.4. Um ponto
¯
x ∈ R
n
é chamado zero de T : R
n
⇒ R
n
quando 0 ∈ T (
¯
x).
Definição 2.5. Seja T : R
n
⇒ R
n
. Dizemos que T é monótono quando para quaisquer
x, y ∈ R
n
, u ∈ T (x) e v ∈ T(y) tem-se
x − y, u − v 0. (2.2)
Observação 2.2. T é estritamente monótono se a desigualdade (2.2) é estrita para x = y.
Proposição 2.1. Sejam T
1
: R
n
⇒ R
n
e T
2
: R
n
⇒ R
n
operadores monótonos, tais que
dom(T
1
) ∩ dom(T
2
) = ∅. Então T
1
+ T
2
é um operador monótono.
Demonstração. Sejam x, y ∈ R
n
, u ∈ (T
1
+ T
2
)(x) e v ∈ (T
1
+ T
2
)(y). Então, para
u ∈ (T
1
+ T
2
)(x) = T
1
(x) + T
2
(x), existem u
1
∈ T
1
(x) e u
2
∈ T
2
(x) tais que u = u
1
+ u
2
.
Analogamente, existem v
1
∈ T
1
(y) e v
2
∈ T
2
(y) tais que v = v
1
+ v
2
. Como T
1
e T
2
são
operadores monótonos, tem-se u
1
− v
1
, x − y 0 e u
2
− v
2
, x − y 0.
Portanto,
u − v, x − y = u
1
+ u
2
− v
1
− v
2
, x − y
= u
1
− v
1
, x − y + u
2
− v
2
, x − y 0.
Logo,T
1
+ T
2
é um operador monótono.
Exemplo 2.2. Seja ∂f : R
n
⇒ R
n
, onde f é uma função convexa própria semicontínua
inferiormente. Então ∂f é um operador monótono.
De fato, sejam x, y ∈ R
n
, ξ ∈ ∂f(x) e η ∈ ∂f(y). Pela definição de ∂f, obtemos
ξ, y − x f(y) − f(x) (2.3)
Capítulo 2. Operadores Monótonos 27
−η, y − x = η, x − y f(x) − f(y). (2.4)
Então, somando (2.3) e (2.4) obtemos
ξ, y − x − η, y − x 0
Logo,
ξ − η, y − x 0 ⇒ ξ − η, x − y 0.
Portanto, ∂f é um operador monótono.
Definição 2.6. Um operador T : R
n
⇒ R
n
é chamado monótono maximal quando
i) T é monótono
ii) Para todo T
operador monótono tal que T(x) ⊂ T
(x) para todo x ∈ R
n
, tem-se
T = T
.
Teorema 2.1. Sejam T
1
: R
n
⇒ R
n
e T
2
: R
n
⇒ R
n
operadores monótonos maximais
tais que (domT
1
) ∩ (domT
2
)
0
= ∅ .
i) Então T
1
+ T
2
é um operador monótono maximal.
Em adição, temos.
ii) Se T
2
é o subdiferencial de uma função convexa própria fechada e T
2
é sobrejetivo,
então T
1
+ T
2
é sobrejetivo.
Demonstração. Ver [3].
A seguir provaremos que T = ∂f : R
n
⇒ R
n
é um operador monótono maximal.
Sejam f : R
n
→ R e x
0
∈ R
n
, defina a função F : R
n
→ R por
F(x) := f(x) +
1
2
x − x
0
2
. (2.5)
Mostraremos agora que F possui um único minimizador.
De fato, considere h(x) =
1
2
x − x
0
2
, ∀ x ∈ R
n
, então F(x) = f(x) + h(x), ∀ x ∈ R
n
.
Como f convexa e h é estritamente convexa, temos pela Proposição 1.1 que F = f + h é
estritamente convexa.
Temos que F é coerciva em R
n
pelo exemplo 1.1. Com isso, temos que F possui um
minimizador global. Sendo F estritamente convexa, esse minimizador é único.
Assim, podemos definir prox
f
: R
n
→ R
n
, dado por
prox
f
(x
0
) := argmin{f(x) +
1
2
x − x
0
2
}. (2.6)
Capítulo 2. Operadores Monótonos 28
Lema 2.1.1. Sejam f : R
n
→ R uma função convexa semicontínua inferiormente e
x, y, z ∈ R
n
. As seguintes condições são equivalentes:
i) z = x + y e f(x) + f
∗
(y) = x, y;
ii) x = prox
f
(z) e y = prox
f
∗
(z).
Demonstração. Faremos algumas considerações preliminares antes de provarmos as equi-
valências. Sendo h(x) =
1
2
x − x
0
2
, temos que F = f + h. Fazendo x = prox
f
(z), temos
que x é um minimizador da função F se, e somente se, 0 ∈ ∂F(x), o que é equivalente a
0 ∈ (∂f(x) + ∂h(x)). Mas, ∇h(x) = x − z, isto implica
x = prox
f
(z) ⇔ 0(∈ ∂f(x) + {x − z}), (2.7)
ou seja, existe y ∈ ∂f(x) tal que z = x + y. Analogamente, podemos mostrar que
y = prox
∗
f
(z). (2.8)
Isto é, existe x ∈ ∂f
∗
(y) tal que z = x + y. O Teorema 1.10 e a Proposição 1.5 implicam
y ∈ ∂f(x) ⇔ f(x) + f
∗
(y) = x, y ⇔ x ∈ ∂f
∗
(y). (2.9)
(i) ⇒ (ii) Por hipótese z = x+y e f(x)+f
∗
(y) = x, y. Então, da equação (2.9) obtemos
y ∈ ∂f(x) e x ∈ ∂f
∗
(y).
Combinando estes resultados com (i),(2.7) e (2.8) obtemos
x = prox
f
(z) e y = prox
∗
f
(z).
(i) ⇐ (ii) Seja x = prox
f
(z). De (2.7) obtemos a existência de um y
0
∈ ∂f(x) tal que
z = x + y
0
. Observemos a equação (2.9) implica
x ∈ ∂f(y
0
) e f(x) + f
∗
(y
0
) = x, y
0
.
Daí, combinando esse resultado com (2.8) obtemos y
0
= prox
∗
f
(z) = y. Segue que
z = x + y e f(x) + f
∗
(y) = x, y.
Teorema 2.2. Se f : R
n
→ R é um função convexa semicontínua inferiormente, então
∂f : R
n
⇒ R
n
é um operador monótono maximal.
Capítulo 2. Operadores Monótonos 29
Demonstração. Pelo exemplo 2.2, ∂f é um operador monótono. Seja T : R
n
⇒ R
n
um operador monótono tal que ∂f(x) ⊂ T(x), para todo x ∈ R
n
. Provemos agora que
T(x) ⊂ ∂f(x), para todo x ∈ R
n
.
Dados x
0
, y
0
∈ R
n
, com y
0
∈ T (x
0
) e y ∈ T (x). Como T é monótono, obtemos
x − x
0
, y − y
0
0, (2.10)
para todo x, y ∈ R
n
.
Considere x
1
= prox
f
(x
0
+ y
0
) e y
1
= prox
f
∗
(x
0
+ y
0
). Pelo Lema 2.1.1, x
0
+ y
0
= x
1
+ y
1
e f(x
1
) + f
∗
(y
1
) = x
1
, y
1
.
Então, pelo Teorema 1.10, y
1
∈ ∂f(x
1
) ⊂ T (x
1
). Daí, tomando x = x
1
e y = y
1
em (2.10),
obtemos
x
1
− x
0
, y
1
− y
0
0. (2.11)
Assim,
0 x
1
− x
0
, x
0
− x
1
= −x
1
− x
0
, x
1
− x
0
= −x
1
− x
0
2
.
Segue que, x
1
= x
0
. Portanto, y
0
= y
1
∈ ∂f(x
1
) = ∂f(x
0
).
Como x
0
e y
0
são arbitrários, tem-se que T (x) ⊂ ∂f(x), ∀ x ∈ R
n
.
Então, ∂f(x) = T (x), ∀ x ∈ R
n
. Logo, ∂f : R
n
→ P(R
n
) é um operador monótono
maximal.
Exemplo 2.3. Seja C um subconjunto convexo e fechado do R
n
. A aplicação
P
C
(x) : R
n
→ C que associa cada x ∈ R
n
o ponto de C mais próximo de x é chamada de
projeção de x sobre C. Essa aplicação é um exemplo de operador monótono maximal que
não é o subdiferencial de uma função convexa semicontínua inferiormente.
2.2 Operadores Paramonótonos
Definição 2.7. Seja T : R
n
→ R
n
um operador. Diz-se que T é paramonótono quando é
monótono e T (x) − T (y), x − y = 0 implica T(x) = T(y).
Para operadores ponto-conjunto temos a seguinte definição.
Definição 2.8. Seja T : R
n
⇒ R
n
um operador. Dizemos que T é paramonótono quando
é monótono e u − v, x − y = 0, com u ∈ T (x), v ∈ T(y), implica u ∈ T(y) e v ∈ T (x).
Capítulo 2. Operadores Monótonos 30
Teorema 2.3. Seja T = ∂f(x), com f : R
n
→ R uma função convexa semicontínua
inferiormente. Então T é um operador paramonótono.
Demonstração. Pelo Exemplo 2.2 ∂f é um operador monótono. Dados x, y ∈ R
n
, con-
sidere u − v, x − y = 0, onde u ∈ ∂f(x) e v ∈ ∂f(y). Defina a função
¯
f : R
n
→ R
por
¯
f(z) := f(z) + u, x − z.
Note que,
¯
f é convexa, pois é soma de funções convexas.
Além disso, ∂
¯
f(z) = ∂f(z) − {u} = {w − u; w ∈ ∂f(z)}. Para z = x, tem-se
¯
f(x) = f(x), e
tomando w = u ∈ ∂f(x) implica 0 ∈ ∂
¯
f(x). Assim, x é minimizador de
¯
f em R
n
pelo
Teorema 1.8.
Como u − v, x − y = 0, temos
u, x − y = v, x − y. (2.12)
Sendo u ∈ ∂f(x) temos u, y − x f(y) − f(x), ou seja,
f(x) − f(y) u, x − y. (2.13)
De maneira análoga, como v ∈ ∂f(y), temos
v, x − y f(x) − f(y). (2.14)
Segue de (2.12), (2.13) e (2.14), que f(x) − f(y) = u, x − y.
Logo, f(x) = f(y) + u, x − y =
¯
f(y). Mas,
¯
f(x) = f(x). Então
¯
f(x) =
¯
f(y). Assim, y é
também um minimizador de
¯
f. Pelo Teorema 1.8, temos que 0 ∈ ∂
¯
f(y).
Portanto, 0 = w − u para algum w ∈ ∂f(y), isto é, u ∈ ∂f(y).
Agora definamos,
¯
g : R
n
→ R por
¯
g(z) := f(z) + v, y − z.
Analogamente a
¯
f, mostra-se que
¯
g é convexa e ∂
¯
g(z) = ∂f(z) − {v} = {w − v; w ∈ ∂f(z)}.
Para z = y, tem-se
¯
g(y) = f(y). Tomando w = v ∈ ∂f(y) implica 0 ∈ ∂
¯
g(y). Portanto,
pelo Teorema 1.8, temos que y é um minimizador de
¯
g em R
n
.
De (2.12), (2.13) e (2.14), segue que f(y) = f(x) + v, y − x =
¯
g(x). Mas,
¯
g(y) = f(y).
Logo,
¯
g(y) =
¯
g(x). Assim, x é também um minimizador de
¯
g em R
n
. Então, pelo
Teorema 1.8, temos que 0 ∈ ∂
¯
g(x).
Capítulo 2. Operadores Monótonos 31
Portanto, 0 = w − v para algum w ∈ ∂f(x). Logo, v ∈ ∂f(x). Com isso concluímos que,
sendo ∂f um operador monótono e u − v, x − y = 0, com u ∈ ∂f(x), v ∈ ∂f(y) implica
u ∈ ∂f(y) e v ∈ ∂f(x). Portanto, T = ∂f é um operador paramonótono.
Proposição 2.2. Se T
1
: R
n
⇒ R
n
e T
2
: R
n
⇒ R
n
são operadores paramonótonos, tais
que dom(T
1
) ∩ dom(T
2
) = ∅. Então T
1
+ T
2
é um operador paramonótono.
Demonstração. Sejam x, y ∈ R
n
, u ∈ (T
1
+ T
2
)(x) e v ∈ (T
1
+ T
2
)(y). Então, para
u ∈ (T
1
+ T
2
)(x) = T
1
(x) + T
2
(x), existem u
1
∈ T
1
(x) e u
2
∈ T
2
(x) tais que u = u
1
+ u
2
.
Analogamente, existem v
1
∈ T
1
(y) e v
2
∈ T
2
(y) tais que v = v
1
+ v
2
. Pela Proposição 2.1,
T
1
+ T
2
é um operador monótono.
Ainda mais, se u − v, x − y = 0, então u
1
− u
2
− v
1
− v
2
, x − y = 0, ou seja,
u
1
− v
1
, x − y + u
2
− v
2
, x − y = 0. Sendo T
1
e T
2
monótonos, obtemos que
u
1
− v
1
, x − y = 0 e u
2
− v
2
, x − y = 0. Mas, T
1
e T
2
são paramonótonos, então
u
1
, ∈ T
1
(y), u
2
∈ T
2
(y), v
1
∈ T
1
(x) e v
2
∈ T
2
(x).
Portanto, u = u
1
+ u
2
∈ T
1
(y) + T
2
(y) = (T
1
+ T
2
)(y) e v = v
1
+ v
2
∈ T
1
(x) + T
2
(x) =
(T
1
+ T
2
)(x).
Logo, T
1
+ T
2
é um operador paramonótono.
2.3 Operadores Pseudomonótonos
Definição 2.9. Seja T : R
n
⇒ R
n
um operador tal que dom(T ) é convexo e fechado.
Dizemos que T é pseudomonótono se satisfaz a seguinte condição:
Se para toda sequência {x
k
} ⊂ dom(T ) convergindo para o ponto
¯
x ∈ dom(T ) e todo
u
k
∈ T (x
k
) para todo k ∈ N tem-se
lim sup
k→∞
u
k
, x
k
−
¯
x 0,
então, existe
¯
u ∈ T (
¯
x) tal que
¯
u,
¯
x − y lim inf
k→∞
u
k
, x
k
− y
para todo y ∈ dom(T).
Proposição 2.3. Seja f : R
n
→ R uma função convexa semicontínua inferiormente.
Então T = ∂f : R
n
⇒ R
n
é um operador pseudomonótono.
Capítulo 2. Operadores Monótonos 32
Demonstração. Seja {x
k
} uma sequência em dom(∂f) tal que
lim
k→∞
x
k
=
¯
x ∈ dom(∂f) e lim sup
k→∞
u
k
, x
k
−
¯
x 0, onde u
k
∈ ∂f(x
k
).
Pela definição de subdiferencial, temos u
k
, y−x
k
f(y)−f(x
k
) para todo y ∈ dom(∂f)
e todo k ∈ N. Então,
lim inf
k→∞
u
k
, x
k
− y lim inf
k→∞
[f(x
k
) − f(y)] = f(
¯
x) − f(y). (2.15)
Da convexidade de f, existe
¯
u ∈ ∂f(
¯
x) tal que f(y) f(
¯
x) +
¯
u, y −
¯
x. Assim,
¯
u,
¯
x − y f(
¯
x) − f(y). (2.16)
Portanto de (2.15) e (2.3), existe
¯
u ∈ ∂f(
¯
x) tal que
¯
u,
¯
x − y lim inf
k→∞
u
k
, x
k
− y.
Logo, T = ∂f é pseudomonótono.
Exemplo 2.4. Seja T : R
n
→ R
n
um operador monótono contínuo. Então T é um
exemplo de operador pseudomonótono que não é o subdiferencial de uma função convexa
semicontínua inferiormente.
Proposição 2.4. Sejam T , S : R
n
⇒ R
n
operadores pseudomonótonos tais que
dom(T) ∩ dom(S) = ∅. Então T + S é pseudomonótono.
Demonstração. Seja {x
k
} uma sequência em dom(T + S) tal que
lim
k→∞
x
k
=
¯
x ∈ dom(T + S) e
lim sup
k→∞
u
k
, x
k
−
¯
x 0, (2.17)
onde u
k
∈ (T + S)(x
k
).
Seja y ∈ dom(T +S)(x
k
). Então, existem u
k
T
∈ T (x
k
) e u
k
S
∈ S(x
k
) tal que u
k
= u
k
T
+u
k
S
.
De (2.17), lim sup
k→∞
u
k
T
+ u
k
S
, x
k
−
¯
x 0. Então
lim sup
k→∞
u
k
T
, x
k
−
¯
x lim sup
k→∞
u
k
T
+ u
k
S
, x
k
−
¯
x 0,
lim sup
k→∞
u
k
S
, x
k
−
¯
x lim sup
k→∞
u
k
T
+ u
k
S
, x
k
−
¯
x 0.
Como T e S são pseudomonótonos, existem
¯
u
T
∈ T (
¯
x) e
¯
u
S
∈ S(
¯
x) tais que
¯
u
T
,
¯
x − y lim inf
k→∞
u
k
T
, x
k
− y,
¯
u
S
,
¯
x − y lim inf
k→∞
u
k
S
, x
k
− y,
para todo y ∈ dom(T + S).
Capítulo 2. Operadores Monótonos 33
Logo,
¯
u
T
+
¯
u
S
,
¯
x − y lim inf
k→∞
u
k
T
+ u
k
S
, x
k
− y.
Seja
¯
u =
¯
u
T
+
¯
u
S
∈ T (
¯
x) + S(
¯
x) = (T + S)(
¯
x). Então,
¯
u,
¯
x − y lim inf
k→∞
u
k
T
+ u
k
S
, x
k
− y,
para todo y ∈ dom(T + S). Portanto, T + S é pseudomonótono.
Capítulo 3
O Algoritmo do Ponto Proximal
3.1 O Algoritmo do Ponto Proximal para Operadores
Monótonos Maximais(APPOMM)
Seja f : R
n
→ R uma função convexa semicontínua inferiormente. O Algoritmo do Ponto
Proximal (ver Apêndice) gera, para um ponto de inicial x
0
∈ R
n
, a sequência {x
k
} ⊂ R
n
pela iteração
x
k+1
:= arg min
x∈R
n
{f(x) + λ
k
x − x
k
2
},
onde {λ
k
} é uma sequência de números positivos satifazendo,
0 < λ
k
¯
λ,
para algum
¯
λ > 0 e · é a norma euclideana. A sequência das iteradas converge para
solução do problema
min
x∈R
n
f(x). (3.1)
Equivalentemente, temos pelo Teorema1.8
0 ∈ ∂f(x
k+1
) + 2λ
k
(x
k+1
− x
k
),
ou seja
2λ
k
(x
k
− x
k+1
) ∈ ∂f(x
k+1
),
assim
x
k
∈ (I +
1
2λ
k
∂f)(x
k+1
). (3.2)
34
Capítulo 3. O Algoritmo do Ponto Proximal 35
Motivados por essa observação e lembrando que o subdiferencial ∂f de uma função convexa
semicontínua inferiormente , é um operador monótono maximal, podemos extender o
Algoritmo do Ponto Proximal para encontrar zeros de Operadores Monótonos Maximais
T : R
n
⇒ R
n
.
O Algoritmo do Ponto Proximal para Operadores Monótonos Maximais (APPOMM) gera
uma sequência {x
k
} ⊂ R
n
, da seguinte forma
x
0
∈ R
n
,
x
k
∈ (I +
1
λ
k
T)(x
k+1
),
ou seja
x
k+1
∈ (I +
1
λ
k
T)
−1
(x
k
),
onde λ
k
é uma sequência de números positivos satisfazendo
0 < λ
k
¯
λ,
para algum
¯
λ > 0.
Observação 3.1. Para mostrarmos a bem definição e a convergência desse algoritmo
utilizaremos a norma euclideana.
Agora, veremos algumas definições e resultados que serão úteis na análise de con-
vergência do (APPOMM).
Definição 3.1. Uma sequência {y
k
} ⊂ R
n
é dita Fejér convergente a um conjunto
U ⊂ R
n
, com respeito a norma euclidiana, se
y
k+1
− u y
k
− u, ∀ k 0 e ∀ u ∈ U. (3.3)
Proposição 3.1. Se {y
k
} é uma sequência Fejér convergente a um conjunto U = ∅, então
{y
k
} é limitada. Além disso se um ponto de acumulação
¯
y de {y
k
} pertence a U, então
lim
k→∞
y
k
=
¯
y.
Demonstração. Seja u ∈ U, um ponto fixado. Como {y
k
} é Fejér convergente a U, temos
que
y
k+1
− u y
k
− u ... y
0
− u.
Capítulo 3. O Algoritmo do Ponto Proximal 36
Portanto, {y
k
} está contida na bola B = B(u, y
0
− u). Logo, {y
k
} é limitada.
Para a segunda parte considere uma subsequência {y
k
j
} de {y
k
}, tal que lim
k→∞
y
k
j
=
¯
y.
Como
¯
y ∈ U e {y
k
} é Fejér convergente, pela Definição 3.1 a sequência {y
k
−
¯
y} é
não-crescente e não-negativa, portanto convergente.
Como, a subsequência {y
k
j
−
¯
y} converge a zero, segue que {y
k
−
¯
y} converge a zero.
Isto é, lim
k→∞
y
k
−
¯
y = 0. Logo, lim
k→∞
y
k
=
¯
y.
Definição 3.2. Seja T : R
n
⇒ R
n
um operador ponto-conjunto, dizemos que
i) T é sobrejetivo quando, para todo y ∈ R
n
, existe x ∈ R
n
, tal que y ∈ T (x).
ii) T é injetivo se, para x = y tivermos T (x) ∩ T (y) = ∅.
Teorema 3.1. (Teorema de Minty)
Se T : R
n
⇒ R
n
é um operador monótono maximal e λ > 0, então o operador I + λT é
injetivo e sobrejetivo.
Demonstração. Ver [13].
O Teorema 3.1 garante que (APPOMM) está bem definido, como veremos na Proposição
seguinte.
Proposição 3.2. A sequência {x
k
} gerada pelo (APPOMM) está bem definida.
Demonstração. De fato, seja x
0
∈ R
n
, e seja x
k
∈ R
n
, sendo I + λT sobrejetivo, temos
que existe x
k+1
∈ R
n
para todo k 0 tal que
x
k
∈ (I +
1
λ
k
T)(x
k+1
),
portanto
x
k+1
∈ (I +
1
λ
k
T)
−1
(x
k
).
A injetividade de (I + λT ) garante a unicidade de x
k+1
.
Lema 3.1.1. Se lim
k→∞
y
k
=
¯
y, lim
k→∞
z
k
=
¯
z, T é um operador monótono maximal e
y
k
∈ T (z
k
), então
¯
y ∈ T (
¯
z).
Demonstração. Defina,
T
(z) =
T(z), se z =
¯
z
T(
¯
z) ∪ {
¯
y}, se z =
¯
z
. (3.4)
Capítulo 3. O Algoritmo do Ponto Proximal 37
Afirmação: T
é monótono. Então, precisamos verificar que:
y − y
, z − z
0, ∀ z, z
, ∀ y ∈ T
(z) e ∀ y
∈ T
(z
). (3.5)
Da definição de T
e T sendo monótono, basta verificarmos (3.5) para y
=
¯
y e z
=
¯
z.
Por hipótese temos, {y
k
} ∈ T (z
k
), portanto
y − y
k
, z − z
k
0, ∀ z, ∀ y ∈ T (z). (3.6)
Tomando o limite em (3.6) quando k → ∞, obtemos
y −
¯
y, z −
¯
z 0, ∀ z, ∀ y ∈ T (z).
Logo, T
é um operador monótono.
Como T(x) ⊂ T
(x), ∀ x ∈ R
n
e por hipótese T é monótono maximal, concluímos que
T = T
.
Em particular, T(
¯
z) = T
(
¯
z) = T (
¯
z) ∪ {
¯
y}. Logo,
¯
y ∈ T (
¯
z).
O lema acima mostra que os Operadores Monótonos Maximais são fechados.
Veremos agora resultados que garantem a convergência do (APPOMM).
Lema 3.1.2. Sejam T : R
n
⇒ R
n
monótono maximal e o conjunto
U = {x ∈ R
n
; 0 ∈ T (x)} não-vazio. Então, a sequência {x
k
} gerada pelo (APPOMM)
satisfaz a seguinte desigualdade
x
k+1
−
¯
x
2
x
k
−
¯
x
2
− x
k+1
− x
k
2
, ∀ k 0 e ∀
¯
x tal que 0 ∈ T (
¯
x).
Demonstração. De fato, seja
¯
x ∈ U, então
x
k
−
¯
x
2
= (x
k
− x
k+1
) + (x
k+1
−
¯
x)
2
= x
k
− x
k+1
2
+ x
k+1
−
¯
x
2
+ 2x
k
− x
k+1
, x
k+1
−
¯
x.
Assim,
x
k
−
¯
x
2
− x
k
− x
k+1
2
− x
k+1
−
¯
x
2
= 2
1
λ
k
λ
k
(x
k
− x
k+1
), x
k+1
−
¯
x.
Como,
x
k+1
∈ (I +
1
λ
k
T)
−1
(x
k
),
temos
λ
k
(x
k
− x
k+1
) ∈ T (x
k+1
).
Capítulo 3. O Algoritmo do Ponto Proximal 38
Então, como 0 ∈ T(
¯
x), temos pela monotonicidade de T
λ
k
(x
k
− x
k+1
), x
k+1
−
¯
x = λ
k
(x
k
− x
k+1
) − 0, x
k+1
−
¯
x 0.
Portanto,
x
k
−
¯
x
2
− x
k
− x
k+1
2
− x
k+1
−
¯
x
2
0.
Logo,
x
k+1
−
¯
x
2
x
k
−
¯
x
2
− x
k
− x
k+1
2
, ∀ k 0 e ∀
¯
x tal que 0 ∈ T (
¯
x).
Lema 3.1.3. Sejam T : R
n
⇒ R
n
monótono maximal e o conjunto
U = {x ∈ R
n
; 0 ∈ T(x)} não-vazio. Então, lim
k→∞
(x
k+1
− x
k
) = 0, onde {x
k
} é a sequência
gerada pela (APPOMM).
Demonstração. Do Lema 3.1.2, temos
0 x
k+1
− x
k
2
x
k
−
¯
x
2
− x
k+1
−
¯
x
2
, ∀ k 0. (3.7)
Mas, 0 x
k+1
−
¯
x
2
x
k
−
¯
x
2
, implicando que a sequência {x
k
−
¯
x} é não-crescente
e não-negativa. Portanto, convergente.
Assim,
lim
k→∞
(x
k
−
¯
x
2
− x
k+1
−
¯
x
2
) = 0.
Logo, passando o limite em (3.7) quando k → ∞, obtemos
lim
k→∞
(x
k+1
− x
k
) = 0.
Lema 3.1.4. Sejam T : R
n
⇒ R
n
monótono maximal e o conjunto
U = {x ∈ R
n
; 0 ∈ T(x)} não-vazio. Então, a sequência {x
k
} gerada por (APPOMM)
possui pontos de acumulação e todos pertencem a U.
Demonstração. Pelo Lema 3.1.2, {x
k
} é Fejér convergente a U, portanto é limitada pela
Proposição 3.1, então {x
k
} possui pontos de acumulação. Sejam
ˆ
x um ponto de acumulação
de {x
k
} e {x
k
j
} uma subsequência de {x
k
} tal que lim
k→∞
x
k
j
=
ˆ
x.
Por hipótese, temos que
x
k+1
∈ (I +
1
λ
k
T)
−1
(x
k
),
Capítulo 3. O Algoritmo do Ponto Proximal 39
então
λ
k
j
(x
k
j
− x
k
j
+1
) ∈ T (x
k
j
+1
).
Pelo Lema 3.1.3 lim
k→∞
(x
k
j
− x
k
j
+1
) = 0 e λ
k
j
¯
λ, obtemos
lim
k→∞
λ
k
j
(x
k
j
− x
k
j
+1
) = 0.
Daí, aplicando o Lema 3.1.1, para
¯
y = 0, y
k
= λ
k
j
(x
k
j
− x
k
j
+1
), z
k
= x
k
j
+1
e
¯
z =
ˆ
x,
temos que 0 ∈ T (
ˆ
x). Logo,
ˆ
x ∈ U.
Teorema 3.2. Sejam T : R
n
⇒ R
n
monótono maximal e o conjunto
U = {x ∈ R
n
; 0 ∈ T (x)} não-vazio. Então, a sequência {x
k
}, gerada por (APPOMM),
converge a um elemento de U.
Demonstração. Pelo Lema 3.1.2, {x
k
} é Fejér convergente a U. Assim, pela
Proposição 3.1 {x
k
} é limitada. Seja
ˆ
x ponto de acumulação de {x
k
}. Pelo Lema 3.1.4,
ˆ
x ∈ U. Portanto lim
k→∞
x
k
=
ˆ
x pela Proposição 3.1. Logo, {x
k
} converge a um elemento de
U.
Capítulo 4
Algoritmo do Ponto Proximal com
Distâncias de Bregman para o
Problema de Desigualdade Variacional
4.1 Problema de Desigualdade Variacional
A extensão natural do problema
min f(x) sujeito a x ∈ C, (4.1)
(onde C ⊂ R
n
é fechado e convexo) a operadores monótonos é chamado o problema de
desigualdade variacional, definido segundo a definição abaixo.
Definição 4.1. Dados T : R
n
⇒ R
n
um operador monótono maximal e C ⊂ R
n
um
conjunto convexo e fechado o Problema de Desigualdade Variacional VIP(T, C) consiste
em encontrar z ∈ C tal que existe u ∈ T(z) satisfazendo
u, x − z 0 (4.2)
para todo x ∈ C.
Observação 4.1. Se T = ∂f, para f : R
n
→ R convexa, temos que u ∈ T (z) = ∂f(z) se,
e somente se, 0 u, x − z f(x) − f(z) para todo x ∈ C, e portanto z minimiza f em
C. Assim, o problema VIP(T , C) generaliza o problema de minimizar funções convexas
em conjuntos convexos.
40
Capítulo 4. Algoritmo do Ponto Proximal com Distâncias de Bregman
para o Problema de Desigualdade Variacional 41
4.2 Algoritmo do Ponto Proximal Generalizado para
o VIP(T, C)
Seja f : R
n
→ R uma função convexa. O Algoritmo do Ponto Proximal com Distância de
Bregman gera( Ver apêndice), para um ponto inicial x
0
∈ S, a sequência {x
k
} ⊂ S pela
iteração
x
k+1
:= arg min
x∈S
{f(x) + λ
k
D
h
(x, x
k
)},
onde h é uma função de Bregman com zona S e {λ
k
} é uma sequência de números positivos
satisfazendo,
0 < λ
k
¯
λ,
para algum
¯
λ > 0. A sequência das iteradas converge para solução do problema
min f(x) sujeito a x ∈ S, (4.3)
com S ⊂ R
n
aberto e convexo, S o fecho de S, e f contínua em S.
Equivalentemente, temos pelo Teorema 1.8
0 ∈ ∂[f(·) + λ
k
D
h
(·, x
k
)](x
k+1
),
ou seja
0 ∈ [∂f(·) + λ
k
∂
x
D
h
(·, x
k
)](x
k+1
).
Com essa observação e lembrando que o subdiferencial de uma função convexa semi-
contínua inferiormente ∂f é um operador monótono maximal, podemos estender o Al-
goritmo do Ponto Proximal com Distância de Bregman para resolver o VIP(T , C), onde
T : R
n
⇒ R
n
é um operador monótono maximal.
O algoritmo do ponto proximal generalizado para o VIP(T , C) é definido da seguinte
forma.
Considere uma função de Bregman h com zona C
0
e uma sequência de números positivos
{λ
k
} limitada acima por
¯
λ > 0. Seja {x
k
} a sequência definida por
Inicialização:
x
0
∈ C
0
. (4.4)
Iteração: Dado x
k
∈ C
0
, defina T
k
: R
n
⇒ R
n
por T
k
(·) = T (·) + λ
k
∂
x
D
h
(·, x
k
) e
encontre x
k+1
∈ C
0
tal que
0 ∈ T
k
(x
k+1
). (4.5)
Capítulo 4. Algoritmo do Ponto Proximal com Distâncias de Bregman
para o Problema de Desigualdade Variacional 42
Equivalentemente a (4.5) temos
x
k+1
∈ [∂
x
D
h
(·, x
k
) +
1
λ
k
T]
−1
(x
k
) (4.6)
e também equivalente a (4.5) temos
λ
k
[∇h(x
k
) − ∇h(x
k+1
)] ∈ T (x
k+1
) (4.7)
pela Proposição 1.6 (ii).
Apresentaremos agora alguns resultados que utilizaremos na análise de convergência do
algoritmo do ponto proximal generalizado para o VIP(T , C), para isso suponhamos que o
VIP(T, C) possua soluções.
Teorema 4.1. Seja {x
k
} a sequência gerada por (4.4) e (4.5). Suponha que
dom(T) ∩ C
0
= ∅ e a função de Bregman h é zona coerciva com zona C
0
. Então {x
k
} está
bem definida e contida em C
0
.
Demonstração. Faremos a prova por indução sobre k. De (4.4) x
0
∈ C
0
. Suponha que
x
k
∈ C
0
. Seja B
k
(·) := λ
k
∂
x
D
h
(·, x
k
), temos dom(B
k
) = C
0
(ver Apêndice Lema A.2.1
seção A.2).
Assim, T
k
= T + B
k
e dom(T ) ∩ dom(B
k
) = dom(T) ∩ C
0
= ∅. Então, T
k
é monótono
ma-
ximal pela Teorema 2.1 (i). Sendo h estritamente convexa por (B
2
), temos que B
k
é
estritamente monótono, então T
k
é estritamente monótono.
Como h é zona coerciva, B
k
é sobrejetivo. Então, pelo Teorema 2.1 (ii) T
k
é sobrejetivo.
Logo, T
k
possui um zero em dom(T
k
), que é único pela monotonicidade estrita de T
k
.
Denotemos este zero por x
k+1
.
Como dom(T
k
) = dom(T) ∩ dom(B
k
) = dom(T) ∩ C
0
e x
k+1
pertence a dom(T
k
),
obtemos que x
k+1
∈ C
0
para todo k.
Portanto, {x
k
} está bem definida e contida em C
0
.
Em posse das hipóteses do Teorema 4.1, temos os seguintes lemas.
Lema 4.2.1. A sequência {x
k
} gerada por (4.4) e (4.5) satisfaz a seguinte desigualdade
D
h
(
¯
x, x
k+1
) D
h
(
¯
x, x
k
) − D
h
(x
k+1
, x
k
)
para todo k e cada solução
¯
x do VIP(T, C). Consequentemente a sequência {D
h
(
¯
x, x
k
)} é
não crescente.
Capítulo 4. Algoritmo do Ponto Proximal com Distâncias de Bregman
para o Problema de Desigualdade Variacional 43
Demonstração. De (4.7) , temos λ
k
[∇h(x
k
) − ∇h(x
k+1
)] ∈ T (x
k+1
). Então, existe
u
k
∈ T (x
k+1
) tal que
u
k
= λ
k
[∇h(x
k
) − ∇h(x
k+1
)] ∈ T (x
k+1
). (4.8)
Pelo item (i) da Proposição 1.6, D
h
(x, y) − D
h
(x, z) − D
h
(z, y) = ∇h(y) −∇h(z), z− x,
para cada x ∈ C e todo y, z ∈ C
0
. Tomando y = x
k
, z = x
k+1
e x = y, obtemos
∇h(x
k
) − ∇h(x
k+1
), x
k+1
− y = D
h
(y, x
k
) − D
h
(y, x
k+1
) − D
h
(x
k+1
, x
k
). (4.9)
De (4.8) e (4.9), tem-se
u
k
, x
k+1
− y = λ
k
[D
h
(y, x
k
) − D
h
(y, x
k+1
) − D
h
(x
k+1
, x
k
)]. (4.10)
Seja
¯
x solução do VIP(T , C) e tome v ∈ T (
¯
x) tal que
v, x −
¯
x 0, para todo x ∈ C. (4.11)
Como T é monótono, u
k
− v, x
k+1
−
¯
x 0. Assim de (4.11), temos
u
k
, x
k+1
−
¯
x v, x
k+1
−
¯
x 0. (4.12)
Tomando y =
¯
x em (4.10) e usando (4.12), obtemos
D
h
(
¯
x, x
k
) − D
h
(
¯
x, x
k+1
) − D
h
(x
k+1
, x
k
) 0.
Daí, sendo D
h
não negativa, temos
D
h
(
¯
x, x
k+1
) D
h
(
¯
x, x
k
).
Lema 4.2.2. A sequência {x
k
} gerada por (4.4) e (4.5) é limitada e possui pontos de
acumulação.
Demonstração. Pelo Lema 4.2.1 temos que a sequência {D
h
(
¯
x, x
k
)} é não crescente e não
negativa. Então, D
h
(
¯
x, x
k+1
) D
h
(
¯
x, x
k
) ... D
h
(
¯
x, x
0
) para todo k e todo
¯
x solução
do VIP(T , C) . Portanto, {x
k
} está contida no conjunto {x ∈ C; D
h
(
¯
x, x) D
h
(
¯
x, x
0
)} que
é limitado por (B
3
). Logo, {x
k
} é limitada e possui pontos de acumulação.
Lema 4.2.3. lim
k→∞
D
h
(x
k+1
, x
k
) = 0.
Capítulo 4. Algoritmo do Ponto Proximal com Distâncias de Bregman
para o Problema de Desigualdade Variacional 44
Demonstração. Pelo Lema 4.2.1
, 0 D
h
(x
k+1
, x
k
) D
h
(
¯
x, x
k
) − D
h
(
¯
x, x
k+1
), (4.13)
para todo
¯
x solução do VIP(T , C). Como {D
h
(
¯
x, x
k
)} é não crescente pelo Lema 4.2.1 e
limitada por baixo (D
h
0), temos que {D
h
(
¯
x, x
k
)} é convergente. Então,
lim
k→∞
[D
h
(
¯
x, x
k
) − D
h
(
¯
x, x
k+1
)] = 0. (4.14)
Assim, de (4.13) e (4.14), segue que lim
k→∞
D
h
(x
k+1
, x
k
)=0.
Lema 4.2.4. Seja T : R
n
⇒ R
n
pseudomonótono. Se
˜
x é um ponto de acumulação de
{x
k
}, então existe
˜
u ∈ T (
˜
x) tal que
˜
u, x
∗
−
˜
x = 0, para todo x
∗
solução do VIP(T , C).
Demonstração. Seja
˜
x um ponto de acumulação de {x
k
} e {x
k
j
} uma subsequência de {x
k
}
tal que lim
k→∞
x
k
j
=
˜
x ∈ C, pois C é fechado.
Tomando y =
˜
x e k = k
j
em (4.10), obtemos
u
k
j
, x
k
j
+1
−
˜
x = λ
k
j
[D
h
(
˜
x, x
k
j
) − D
h
(
˜
x, x
k
j
+1
) − D
h
(x
k
j
+1
, x
k
j
)]. (4.15)
Observe que
1) {x
k
j
+1
} é limitada pelo Lema 4.2.2.
2) lim
k→∞
x
k
j
=
˜
x .
3) lim
k→∞
D
h
(x
k
j
+1
, x
k
j
) = 0 pelo Lema 4.2.3.
Então, aplicando (B
5
) para as sequências {x
k
j
+1
} e {x
k
j
}, temos
lim
k→∞
x
k
j
+1
=
˜
x. (4.16)
Em posse de (4.16) e (2), podemos aplicar (B
4
) as sequências {x
k
j
+1
} e {x
k
j
}, então
lim
k→∞
D
h
(
˜
x, x
k
j
+1
) = 0 e lim
k→∞
D
h
(
˜
x, x
k
j
) = 0.
Assim,
lim
k→∞
[D
h
(
˜
x, x
k
j
+1
) − D
h
(
˜
x, x
k
j
)] = 0. (4.17)
Como {λ
k
} é limitada. Segue de (3) e (4.17) e fazendo k tender a ∞ em (4.15) que
lim sup
k→∞
u
k
j
, x
k
j
+1
−
˜
x = lim
k→∞
u
k
j
, x
k
j
+1
−
˜
x = 0. (4.18)
Capítulo 4. Algoritmo do Ponto Proximal com Distâncias de Bregman
para o Problema de Desigualdade Variacional 45
onde u
k
j
∈ T (x
k
j
+1
), para todo j ∈ N.
Sendo T pseudomonótono, então para todo z solução do VIP(T , C) existe
˜
u ∈ T (
˜
x) tal
que
˜
u,
˜
x − z lim inf
k→∞
u
k
j
, x
k
j
+1
− z. (4.19)
Tomando y = z em (4.10)
u
k
, x
k+1
− z = λ
k
[D
h
(z, x
k
) − D
h
(z, x
k+1
) − D
h
(x
k+1
, x
k
)]. (4.20)
Pelo Lema 4.2.1, temos que a sequência {D
h
(z, x
k
)} é não crescente. Sendo {λ
k
} limitada,
então em (4.20), temos
lim
k→∞
u
k
, x
k+1
− z = lim
k→∞
λ
k
[D
h
(z, x
k
) − D
h
(z, x
k+1
) − D
h
(x
k+1
, x
k
)] = 0.
Assim, lim inf
k→∞
u
k
j
, x
k
j
+1
− z = 0. Então, de (4.19), temos
˜
u,
˜
x − z 0, (4.21)
com
˜
u ∈ T (
˜
x).
Por outro lado, como z é solução do VIP(T , C), existe v ∈ T(z) tal que v, y − z 0 para
todo y ∈ C. Além disso, sendo T monótono ,
˜
u − v,
˜
x − z 0. Portanto,
˜
u,
˜
x − z v,
˜
x − z 0. (4.22)
Logo, de (4.21) e (4.22) segue que
˜
u,
˜
x − z = 0, para todo z solução do VIP(T , C).
Os teorema que veremos a seguir garantem que a sequência gerada por (4.4) e (4.5)
converge para uma solução do VIP(T,C).
Teorema 4.2. Seja T : R
n
⇒ R
n
um operador monótono maximal. Considere o problema
VIP(T, C), onde C ⊂ R
n
é convexo e fechado. Seja h uma função de Bregman com zona
C
0
. Suponha que as seguintes condições são válidas:
i) dom(T) ∩ C
0
= ∅.
ii) VIP(T , C) possui soluções.
iii) T é pseudomonótono.
iv) 0 < λ
k
¯
λ, para algum
¯
λ > 0.
v) Ou, h é zona coerciva, ou h é coerciva na fronteira.
Então a sequência {x
k
}, gerada por (4.4) e (4.5), satisfaz:
Capítulo 4. Algoritmo do Ponto Proximal com Distâncias de Bregman
para o Problema de Desigualdade Variacional 46
a) A sequência {D
h
(
¯
x, x
k
)} é não crescente, para toda solução
¯
x de VIP(T , C).
b) {x
k
} é limitada e possui pontos de acumulação.
c) lim
k→∞
D
h
(x
k+1
, x
k
) = 0.
d) Se
ˆ
x é um ponto de acumulação de {x
k
}, então existe
ˆ
u ∈ T (
ˆ
x) tal que
ˆ
u, x
∗
−
ˆ
x = 0,
para toda solução x
∗
do VIP(T , C).
Demonstração. a) Lema 4.2.1
b) Lema 4.2.2
c) Lema 4.2.3
d) Lema 4.2.4.
Teorema 4.3. Seja T : R
n
⇒ R
n
um operador monótono maximal. Considere o problema
VIP(T, C), onde C ⊂ R
n
é convexo e fechado. Seja h uma função de Bregman com zona
C
0
. Suponha que as seguintes condições são válidas:
i) dom(T) ∩ C
0
= ∅.
ii) VIP(T , C) possui soluções.
iii) T é pseudomonótono.
iv) 0 < λ
k
¯
λ, para algum
¯
λ > 0.
v) Ou, h é zona coerciva, ou h é coerciva na fronteira.
vi) T é paramonótono em C.
Então a sequência {x
k
}, gerada por (4.4) e (4.5), converge para uma solução
¯
x do VIP(T, C).
Demonstração. Pelo Lema 4.2.2, {x
k
} possui pontos de acumulação. Seja
¯
x um ponto de
acumulação de {x
k
}. Pelo Lema 4.2.4 existe
¯
u ∈ T (
¯
x) tal que
¯
u, x
∗
−
¯
x = 0, (4.23)
para todo x
∗
solução do VIP(T, C).
Como x
∗
é solução do VIP(T , C) existe u ∈ T (x
∗
) tal que
u, x − x
∗
0 (4.24)
para todo x ∈ C.
Daí, pela monotonicidade de T, u −
¯
u, x
∗
−
¯
x 0, ou seja, por (4.23) e (4.24)
0 =
¯
u, x
∗
−
¯
x u, x
∗
−
¯
x 0, segue que
¯
u, x
∗
−
¯
x = u, x
∗
−
¯
x = 0. (4.25)
Capítulo 4. Algoritmo do Ponto Proximal com Distâncias de Bregman
para o Problema de Desigualdade Variacional 47
De (4.25), u −
¯
u, x
∗
−
¯
x = 0 com u ∈ T (x
∗
),
¯
u ∈ T (
¯
x), então pela paramonotonicidade
de T, obtemos
u ∈ T (
¯
x). (4.26)
Portanto, usando (4.25) e em seguida (4.24), temos
u, x −
¯
x = u, x − x
∗
+ u, x
∗
−
¯
x 0. (4.27)
Logo, por (4.26) e (4.27) concluímos que
¯
x é solução do VIP(T , C).
Seja {x
k
j
} uma subsequência de {x
k
} tal que lim
k→∞
x
k
j
=
¯
x. Então, por (B
4
) lim
k→∞
D
h
(
¯
x, x
k
j
) =
0.
Pelo Lema 4.2.1 a sequência {D
h
(
¯
x, x
k
)} é não crescente e não negativa. Assim {D
h
(
¯
x, x
k
)}
é convergente e com subsequência convergindo a zero. Logo {D
h
(
¯
x, x
k
)} converge a zero.
Então segue de (B
4
) que lim
k→∞
x
k
=
¯
x.
Portanto, a sequência {x
k
} gerada por (4.4) e (4.5), converge para uma solução
¯
x do
VIP(T, C).
Observação 4.2. A convergência do nosso algoritmo pode ser estabelecida retirando a
hipótese de o operador T ser pseudomonótono (ver[19]).
Apêndice A
O Algoritmo do Ponto Proximal
A.1 O Algoritmo do Ponto Proximal em R
n
Neste apêndice , é apresentado o algoritmo do ponto proximal para resolver o problema de
otimização convexa sem restrições (seção A.1) e com restrições (seção A.2). Apresentare-
mos nesta seção o algoritmo do ponto proximal em R
n
que foi proposto por Martinet
(1970) e desenvolvido por Rockafellar, para resolver o problema de otimização convexa
em R
n
como definido em (1).
Com as hipóteses do problema (1) sobre f o Algoritmo do Ponto Proximal gera, para um
ponto de inicial x
0
∈ R
n
, a sequência {x
k
} ⊂ R
n
, pela iteração
x
k+1
= arg min
x∈R
n
{f(x) + λ
k
x − x
k
2
}, (A.1)
onde {λ
k
} é uma sequência de números positivos satifazendo,
0 < λ
k
¯
λ, (A.2)
para algum
¯
λ > 0 e · é a norma euclideana.
O resultado que veremos agora garante que a sequência gerada por (A.1) e (A.2) está
bem definida.
Proposição A.1. A sequência {x
k
} gerada por (A.1) e (A.2) está bem definida.
Demonstração. Defina f
k
(x) := f(x) + λ
k
x − x
k
2
, então lim
x→∞
f
k
(x) = ∞, pois f é
limitada inferiormente. Portanto, f
k
é coerciva. Assim f
k
possui um mínimo, denotemos
este mínimo por x
k+1
.
48
Apêndice A. O Algoritmo do Ponto Proximal 49
Mas, f convexa e λ
k
x − x
k
2
é estritamente convexa, então f
k
é estritamente convexa.
Logo, x
k+1
é único.
Mostraremos que a sequência gerada pelo Algoritmo do Ponto Proximal converge a
uma solução do problema (1)
Lema A.1.1. Suponhamos que f : R
n
→ R é uma função convexa e continuamente dife-
renciável e o conjunto de minimizadores de f, U ⊂ R
n
, é não vazio. Então a sequência
{x
k
} gerada por (A.1) e (A.2) satisfaz a seguinte desigualdade
x
k+1
−
¯
x
2
x
k
−
¯
x
2
− x
k+1
− x
k
2
, ∀ k 0 e ∀
¯
x ∈ U.
Demonstração. Seja
¯
x ∈ U, então
x
k
−
¯
x
2
= (x
k
− x
k+1
) + (x
k+1
−
¯
x)
2
= x
k
− x
k+1
2
+ x
k+1
−
¯
x
2
+ 2x
k
− x
k+1
, x
k+1
−
¯
x.
Como x
k+1
satisfaz (A.1), temos
0 = ∇f
k
(x
k+1
) = ∇f(x
k+1
) + 2λ(x
k+1
− x
k
).
Assim,
x
k
−
¯
x
2
− (x
k
− x
k+1
) − (x
k+1
−
¯
x)
2
= 2x
k
− x
k+1
, x
k+1
−
¯
x
=
1
λ
k
∇f(x
k+1
), x
k+1
−
¯
x
1
λ
k
f(x
k+1
), x
k+1
−
¯
x 0,
onde a primeira desigualdade segue da convexidade de f e a segunda do fato de
¯
x ser
minimizador do problema (1).
Lema A.1.2. Seja f : R
n
→ R uma função convexa e contínuamente diferenciável e o
conjunto de minimizadores de f, U ⊂ R
n
, é não vazio e a sequência {x
k
} gerada por (A.1)
e (A.2). Então, lim
k→∞
(x
k+1
− x
k
) = 0.
Demonstração. Pelo Lema A.1.1, temos
0 x
k+1
− x
k
2
x
k
−
¯
x
2
− x
k+1
−
¯
x
2
.
Como {x
k
} é uma sequência não crescente e não negativa, é convergente. Logo o lado
direito da desigualdade acima converge a zero, e segue o resultado.
Apêndice A. O Algoritmo do Ponto Proximal 50
Lema A.1.3. Sejam f : R
n
→ R uma função convexa e contínuamente diferenciável e o
conjunto de minimizadores de f, U ⊂ R
n
, não vazio. Então a sequência {x
k
} gerada por
(A.1) e (A.2) possui pontos de acumulação e todos pertencem a U.
Demonstração. Pelo Lema A.1.1, temos que {x
k
} é uma sequência Fejér convergente a U,
assim pela Proposição 3.1, ela é limitada.
Seja
¯
x um ponto de acumulação de {x
k
} e {x
k
j
} uma subsequência de {x
k
}, tal que lim
k→∞
x
k
j
=
¯
x. Por (A.1), temos que
0 = ∇f
k
(x
k+1
) = ∇f(x
k+1
) + 2λ(x
k+1
− x
k
),
Assim,
∇f(x
k
j
+1
) = 2λ(x
k
j
− x
k
j
+1
). (A.3)
Pelo Lema A.1.2, segue que
lim
k→∞
x
k
j
+1
= lim
k→∞
x
k
j
=
¯
x.
Usando o fato que λ
k
¯
λ e que f é continuamente diferenciável e aplicando ao limite em
(A.3), obtemos que ∇f(
¯
x) = 0. Portanto pela convexidade de f,
¯
x ∈ U.
Teorema A.1. Seja f : R
n
→ R uma função convexa e contínuamente diferenciável e o
conjunto de minimizadores de f, U ⊂ R
n
, é não vazio. Então a sequência {x
k
} gerada por
(A.1) e (A.2), converge para um ponto x
∗
∈ U.
Demonstração. O Lema A.1.2 garante que a sequência {x
k
} gerada por (A.1) e (A.2) é
Fejér convergente a U e o Lema A.1.3 garante que todos os seus pontos de acumulação
pertencem a U. Portanto, pela Proposição 3.1, a sequência {x
k
} converge a x
∗
∈ U.
A.2 O Algoritmo do Ponto Proximal com Distâncias de
Bregman(APPDB)
Nesta seção apresentaremos o Algoritmo do Ponto Proximal com Distâncias de Bregman
que é uma generalização do algoritmo apresentado na seção anterior, onde é substituida
a norma Euclideana pela distância de Bregman.
O problema de interesse é
min f(x) sujeito a x ∈ S, (A.4)
Apêndice A. O Algoritmo do Ponto Proximal 51
onde S ⊂ R
n
é aberto e convexo, com S o fecho de S, e f contínua em S. O Algoritmo do
Ponto Proximal com Distância de Bregman (APPD) é definido como x
0
∈ S,
x
k+1
:= arg min
x∈S
{f(x) + λ
k
D
h
(x, x
k
)} (A.5)
onde h é uma função de Bregman com zona S e {λ
k
} uma sequência de números positivos
satisfazendo
0 < λ
k
¯
λ, para algum
¯
λ > 0. (A.6)
Prosseguimos com a análise de convergência. Assumimos a partir de agora que (A.4)
tenha soluções de modo que f seja limitada inferiormente em S.
Lema A.2.1. A sequência {x
k
} gerada pelo (APPD) está bem definida e contida em S.
Demonstração. Seja β um limite inferior para f em S e f
k
(x) = f(x)+λ
k
D
h
(x, x
k
). Então,
f
k
(x) β + λ
k
D
h
(x, x
k
) e decorre de (B
3
) que os conjuntos de nível de f
k
são limitados
de modo que a minimização em (A.5) se reduz a um compacto e o mínimo é atingido.
Note que f
k
é estritamente convexa pela convexidade de h e
pela Proposição 1.6 (iii), de modo que o mínimo é único e assim x
k+1
é unicamente
determinado. Em seguida provaremos que x
k+1
∈ S.
É fácil verificar a partir de (A.5) que x
k+1
é único x ∈ S tal que
λ
k
∇h(x
k
) ∈ ∂(f + λ
k
h)(x). (A.7)
Mostraremos que de acordo com (B
6
), ∂(f + λ
k
h)(x) = ∅ para todo x ∈ ∂S, assim, tendo
em conta (A.7) temos x
k+1
∈ S.
De fato, tome x ∈ ∂S e suponha que exista ξ ∈ ∂(f + λ
k
h)(x). Tome z ∈ S e defina
y
t
= (1 − ε
t
)x + ε
t
z (A.8)
com lim
t→∞
ε
t
= 0. Então y
t
∈ S pela convexidade de S e lim
t→∞
y
t
= x.
Assim, de (A.8), da definição de ∂(f + λ
k
h), B
2
e da convexidade de h e f, tem-se
ε
t
ξ, z − x = ξ, y
t
− x
(f + λ
k
h)(y
t
) − (f + λ
k
h)(x)
= f(y
t
) − f(x) + λ
k
(h(y
t
) − h(x))
f(y
t
) − f(x) + λ
k
∇h(y
t
), y
t
− x.
Apêndice A. O Algoritmo do Ponto Proximal 52
Daí, usando (A.8) e da convexidade de f, obtemos
ε
t
ξ, z − x ε
t
(f(z) − f(x)) + λ
k
ε
t
(1 − ε
t
)
∇h(y
t
), z − y
t
. (A.9)
Então, de (A.9)
1 − ε
t
λ
k
[f(x) − f(z) + ξ, z − x] ∇h(y
t
), z − y
t
. (A.10)
Como lim
t→∞
y
t
= x ∈ ∂S, temos por (B
6
) que o lado direito de (A.10) tende a −∞quando t
tende a ∞, enquanto o lado esquerdo tem limite finito. Que é uma contradição, implicando
que ∂(f + λ
k
h) = ∅ para todo x ∈ ∂S e que x
k+1
∈ S.
Lema A.2.2. A sequência {x
k
} gerada pelo (APPD)satisfaz a seguinte
D
h
(
¯
x, x
k+1
) D
h
(
¯
x, x
k
) − D
h
(x
k+1
, x
k
)
para todo k e cada solução
¯
x de (A.4).
Demonstração. Usando a Proposição 1.6 (i) com x =
¯
x, y = x
k
, z = x
k+1
, obtemos
D
h
(
¯
x, x
k
) − D
h
(
¯
x, x
k+1
) − D
h
(x
k+1
, x
k
) = ∇h(x
k
) − ∇h(x
k+1
), x
k+1
−
¯
x. (A.11)
De (A.5)
0 ∈ ∂[f + λ
k
D
h
(·, x
k
)](x
k+1
). (A.12)
De (A.12) e da Proposição 1.6 (ii), temos
λ
k
[∇h(x
k
) − ∇h(x
k+1
)] ∈ ∂f(x
k+1
). (A.13)
Seja y
k
= λ
k
[∇h(x
k
) − ∇h(x
k+1
)]. De (A.11) e da definição de subgradiente, temos
D
h
(
¯
x, x
k
)−D
h
(
¯
x, x
k+1
)−D
h
(x
k+1
, x
k
) =
1
λ
k
y
k
, x
k+1
−
¯
x
1
λ
k
(f(x
k+1
)−f(
¯
x)). (A.14)
Como
¯
x minimiza f em S, temos f(
¯
x) f(x
k+1
), ou seja, 0 f(x
k+1
) − f(
¯
x). Logo,
D
h
(
¯
x, x
k
) − D
h
(
¯
x, x
k+1
) − D
h
(x
k+1
, x
k
) 0.
Lema A.2.3. Se a sequência {x
k
} gerada pelo (APPD) é limitada e lim
k→∞
x
k
j
=
ˆ
x, então
lim
k→∞
x
k
j
+1
=
ˆ
x.
Apêndice A. O Algoritmo do Ponto Proximal 53
Demonstração. Do Lema A.2.2 a sequência {D
h
(
¯
x, x
k
)} é decrescente e não-negativa e
D
h
(x
k+1
, x
k
) D
h
(
¯
x, x
k
) − D
h
(
¯
x, x
k+1
) de modo que
lim
k→∞
D
h
(x
k+1
, x
k
) = 0. (A.15)
Sendo {D
h
(
¯
x, x
k
)} decrescente, temos D
h
(
¯
x, x
k
) D
h
(
¯
x, x
0
). Portanto, por (B
3
) a se-
quência {x
k
} é limitada.
Seja {x
k
j
} uma subsequência de {x
k
} tal que lim
k→∞
x
k
j
=
ˆ
x. Então, por (A.15) temos
lim
k→∞
D
h
(x
k
j
+1
, x
k
j
) = 0. Logo, por (B
5
) lim
k→∞
x
k
j
+1
=
ˆ
x.
Lema A.2.4. A sequência {x
k
} gerada pelo (APPD) possui pontos de acumulação, os
quais são soluções de (A.4).
Demonstração. Tome uma solução
¯
x de (A.4). Pelo Lema A.2.3 existe
ˆ
x um ponto de
acumulação de {x
k
} e {x
k
j
} uma subsequência de {x
k
} tal que lim
k→∞
x
k
j
=
ˆ
x. E ainda
lim
k→∞
x
k
j
+1
=
ˆ
x. De (A.14) e de
0
1
¯
λ
[f(x
k
j
+1
) − f(
¯
x)]
1
λ
k
j
[f(x
k
j
+1
) − f(
¯
x)],
temos
0
1
¯
λ
[f(x
k
j
+1
) − f(
¯
x)] D
h
(
¯
x, x
k
j
) − D
h
(
¯
x, x
k
j
+1
) − D
h
(x
k
j
+1
, x
k
j
). (A.16)
Usando a convergência de {D
h
(
¯
x, x
k
)} e B
5
, segue que
lim
k→∞
[D
h
(
¯
x, x
k
j
) − D
h
(
¯
x, x
k
j
+1
) − D
h
(x
k
j
+1
, x
k
j
)] = 0. (A.17)
Daí, usando a contínuidade de f e (A.17) e fazendo k tender a ∞ em (A.16), obtemos
f(
ˆ
x) = f(
¯
x).
Portanto, sendo que S é fechado e {x
k
} ⊂ S, temos que
ˆ
x ∈ S e
ˆ
x é solução de (A.4).
Teorema A.2. Se o problema (A.4) tem solução e h é froneira coecirva com respeito
a S, então a sequência gerada por (A.5) converge para a solução x
∗
do problema (A.4).
Demonstração. Seja
ˆ
x um ponto de acumulação de {x
k
} e tome a subsequência {x
k
j
} de
{x
k
} tal que lim
k→∞
x
k
j
=
ˆ
x.
Então por (B
4
) lim
k→∞
D
h
(
ˆ
x, x
k
j
) = 0. Pelo Lema A.2.4
ˆ
x é solução de (A.4) e pelo
Lema A.2.2 {D
h
(
ˆ
x, x
k
)} é uma sequência não negativa e decrescente com subsequência
convergindo a 0.
Assim a sequência {D
h
(
ˆ
x, x
k
)} converge a zero, logo por (B
4
) temos lim
k→∞
x
k
=
ˆ
x.
Referências Bibliográficas
[1] AUSLENDER, A., TEBOULLE, M. Asymptotic Cones Functions in Optimization
and Variational Inequalities. Springer Monographs in Mathemathics.
[2] BERTSEKAS, D. P., Nonlinear Programming, Athena Scientific, Belmont. Mas-
sachusetts, 1995.
[3] BRÉZIS H., Opérateurs Monotones Maximaux et Semigrups de Contraction dans les
Espaces de Hilbert, Mathematics Studies 5, North-Holland, New York, 1973.
[4] BURACHIK, R. S., Generalized Proximal Point Methods for the Variational Inequal-
ity Problem, Tese do Grau de Doutor em Matemática, IMPA, Rio de Janeiro, 1995.
[5] BURACHIK, R. S., IUSEM, A. N., A Generalized Proximal Point Algorithm for the
Variational Inequality Problem in a Hilbert Space, SIAM J. Optim., 1991.
[6] DA SILVA, S. R. P., Algoritmo de Ponto Proximal para Otimização em R
n
, Diser-
tação de Mestrado em Matemática, UFG, Goiania, 1999.
[7] FIGUEIREDO, D. G., Equações Elípticas não Lineares, Impa, Rio de Janeiro, 1977.
[8] IUSEM, A. N., Métodos de Ponto Proximal em Otimização, 20
0
Colóquio Brasileiro
de Matemática, IMPA, Rio de Janeiro, 1995.
[9] IUSEM, A. N., On some Properties of Paramonotone Operators, Jurnal of Convex
Analysis, 1998.
[10] IZMAILOV, A., SOLODOV, M., Otimização – volume 1, IMPA, Rio de Janeiro,
2005.
[11] LIMA, E. L., Curso de Análise - volume 2, Sexta Edição, IMPA, Rio de Janeiro,
2006.
54
Referências Bibliográficas 55
[12] MACEDO, A. C., Método de Ponto Proximal Para Otimização, Dissetação de
Mestrado em Matemática, UFG, Goiânia, 2009.
[13] Minty, G., Monotone (nonlinear) operators in Hilbert space, Duke Math. J., 29
(1976), 341–346.
[14] NETO, A. M., Método do Ponto Proximal Usando Distâncias Generalizadas Sep-
aráveis - Reescala e Seleção do Coprimente do Passo, Dissetação de Mestrado em
Matemática, UFG, Goiânia, 2008.
[15] POLYAK, B. T., Introduction to Optimization. Optimization Software, New York
(1987).
[16] ROCKAFELLAR, R. T., Monotone Operators and the Proximal Point Algorithm,
SIAM Journal on Control and Optimization 14, pp. 877-898, 1976.
[17] ROCKAFELLAR, R. T., On the Maximality of Sums of Nonlinear monotone Oper-
ators, Transactions of the American Mathematical Society 149, p.75-88, 1970.
[18] Sissy da S. Souza., P.R. Oliveira., J.X. da Cruz Neto., A. Soubeyran., A proximal
method with separable Bregman distances for quasiconvex minimization over the
nonnegative orthant. European Journal of Operational Research
[19] SOLODOV. M. V., SVAITER. B. F.,AN INEXACT HYBRID GENERALIZED
PROXIMAL POINT ALGORITHM AND SOME NEW RESULTS ON THE THE-
ORY OF BREGMAN FUNCTIONS.
[20] TIEL, J. V., Convex analysis: an introductory text, Royal Netherlands Meteorolog-
ical Institute, 1984.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
