Métodos Matemáticos em Economia, Gil Riella EPPG-FGV 2016

Prévia do material em texto

Notas de Aula - Métodos Matemáticos em Economia
Gil Riella
16 de maio de 2016
ii
Sumário
I Análise Real 1
1 Espaços Métricos 3
1.1 Métrica Relativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Conjuntos Compactos 9
2.1 Compacticidade Sequencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Continuidade 13
3.1 Continuidade e Compacticidade . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Continuidade Uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Correspondências 17
4.1 Continuidade de Correspondências . . . . . . . . . . . . . . . . . . . . . . . 17
4.1.1 Hemicontinuidade Superior . . . . . . . . . . . . . . . . . . . . . . . . 17
4.1.2 Hemicontinuidade Inferior . . . . . . . . . . . . . . . . . . . . . . . . 19
4.1.3 Correspondências de Grá�co Fechado . . . . . . . . . . . . . . . . . . 20
4.2 Teorema do Máximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 Conjuntos Convexos 25
5.1 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6 Hiperplanos e Teoremas de Separação 31
6.1 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
II Otimização 37
7 Otimização Estática 39
7.1 Problemas sem Restrições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.1.1 Otimização de funções diferenciáveis de uma variável . . . . . . . . . 39
7.1.2 Otimização de funções diferenciáveis de múltiplas variáveis . . . . . . 40
7.1.3 Maximização de funções côncavas . . . . . . . . . . . . . . . . . . . . 43
iii
iv SUMÁRIO
7.2 Problemas com Restrições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.2.1 Quali�cação da Restrição . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.3 Otimização Convexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
7.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
8 Teorema de Ponto Fixo de Banach 57
8.1 Sequências de Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
8.2 Espaços Métricos Completos . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
8.3 Contrações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
8.4 Teorema do Ponto Fixo de Banach . . . . . . . . . . . . . . . . . . . . . . . 60
8.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
9 Programação Dinâmica 65
9.1 Princípio da Otimalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9.2 Propriedades da Função Valor . . . . . . . . . . . . . . . . . . . . . . . . . . 71
9.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Referências Bibliográ�cas 75
Agradecimento
Quando eu fui professor da disciplina Métodos Matemáticos emCiências Sociais pela primeira
vez eu não tinha intenção alguma de ter notas de aulas. Estas notas só se tornaram
possíveis, pois, já naquela primeira turma, o excelente aluno Bruno de Albuquerque Furtado
acompanhou o curso e digitou uma primeira versão destas notas a partir do que eu escrevi
no quadro. Eu, e creio que todas as gerações posteriores da disciplina Métodos Matemáticos
em Ciências Sociais, temos esta dívida de gratidão para com o Bruno. Aquele seu esforço
inicial tornou o curso muito melhor para mim e para os alunos.
v
vi SUMÁRIO
Prefácio
Estas são as notas de aula da disciplina de Métodos Matemáticos em Ciências Sociais,
ministrada no programa de pós graduação em economia da Universidade de Brasília (UnB).
vii
viii SUMÁRIO
Parte I
Análise Real
1
Capítulo 1
Espaços Métricos
De�nição 1.1. Seja M um conjunto qualquer. Uma função d :M �M ! R é chamada de
métrica se
(i) d(x; y) � 0; 8x; y 2M ;
(ii) d(x; y) = 0 () x = y;
(iii) d(x; y) = d(y; x); 8x; y 2M ;
(iv) (Desigualdade triangular) d(x; y) � d(x; z) + d(z; y); 8x; y; z 2M .
Se M = Rn, algumas métricas comuns são:
d1(x; y) = kx� yk :=
Pn
i=1 jxi � yij;
d2(x; y) = kx� yk2 :=
pPn
i=1(xi � yi)2;
d1(x; y) = kx� yk1 := maxfjxi � yijg:
Como as métricas acima são construidas através do uso de uma norma, elas ainda
satisfazem:
d(x+ z; y + z) = d(x; y) e d(�x; �y) = j�jd(x; y):
De�nição 1.2. Seja um espaço métrico (M;d). Um conjunto da forma B(x; �) com x 2M
e � > 0 de�nido por B(x; �) := fy 2 M : d(x; y) < �g, é chamado de bola aberta de centro
x e raio �.
O conjunto B(x; �) := fy 2M : d(x; y) � �g é chamado de bola fechada.
Na �gura 1.1, nós vemos a bola aberta de centro 0 e raio 1 no R2 para as três métricas
de�nidas acima.
De�nição 1.3. Dizemos que A �M é um conjunto aberto se para todo x 2 A existe � > 0
tal que B(x; �) � A.
Lema 1.1. Para todo x 2M e � > 0, B(x; �) é um conjunto aberto.
3
4 CAPÍTULO 1. ESPAÇOS MÉTRICOS
Figura 1.1: Bolas abertas em R2
Demonstração. Fixe z 2 B(x; �). Precisamos encontrar 
 > 0 tal que B(z; 
) � B(x; �).
Seja 
 < � � d(x; z). Queremos mostrar que y 2 B(z; 
) implica em y 2 B(x; �). Fixe
y 2 B(z; 
). Isto é, �xe y tal que d(z; y) < 
. Note que d(z; y) < 
 < � � d(x; z), o que
implica em d(z; y)+d(x; z) < �. Pela desigualdade triangular (propriedade (iv) na De�nição
1.1), nós temos que d(x; y) � d(z; y) + d(x; z) < �. �
Exercício 1.1. Mostre que as três métricas que de�nimos acima são equivalentes no sentido
de que, para qualquer A � Rn, A é aberto em (Rn; d1) se e somente se A é aberto em (Rn; d2)
se e somente se A é aberto em (Rn; d1).
Teorema 1.1. Em qualquer espaço métrico (M;d), as seguintes a�rmações são verdadeiras:
(i) M e ? são abertos;
(ii) Se fI�g�2L é uma coleção de conjuntos abertos, então
S
�2L I� é aberto;
(iii) Se fIigni=1 é uma coleção �nita de conjuntos abertos, então
Tn
i=1 Ii é aberto.
Demonstração. (i) É uma consequência imediata da de�nição de conjunto aberto;
(ii) Tome fI�g�2L uma coleção qualquer de conjuntos abertos e pegue x 2
S
�2L I�, i.e.
9�� 2 L tal que x 2 I��. Como I�� é aberto, sabemos que 9� > 0 tal que B(x; �) � I�� �S
�2L I�;
(iii) Seja fIigni=1 uma coleção �nita de conjuntos abertos. Tome x 2
Tn
i=1 Ii, isto é
x 2 Ii 8i 2 N. Como os Ii�s são abertos, para cada i, 9�i > 0 tal que B(x; �i) � Ii. Tome
�� = minf�ig e note que 8i 2 N, B(x; ��) � B(x; �i) � Ii. Ou seja, B(x; ��) �
Tn
i=1 Ii. �
De�nição 1.4. Um conjunto F � M é dito fechado se MnF := fx 2 M : x =2 Fg é um
conjunto aberto.
Teorema 1.2. Seja (M;d) um espaço métrico, as seguintes a�rmações são verdadeiras:
(i) M e ? são conjuntos fechados;
(ii) Se fF�g�2A é uma coleção de conjuntos fechados, então
T
�2A F� é um conjunto fechado;
(iii) Se fFigni=1 é uma coleção �nita de conjuntos fechados, então
Sn
i=1 Fi é fechado.
1.1. MÉTRICA RELATIVA 5
Demonstração. (i) Novamente, isto é uma consequência imediata da de�nição de conjunto
fechado;
(ii) Seja fF�g�2A uma coleção de conjuntos fechados. Observe agora que Mn
T
�2A F� =S
�2A(MnF�). Por de�nição, 8� 2 A, MnF� é aberto e sabemos que a união de conjuntos
abertos é um conjunto aberto e, consequentemente,
T
�2A F� é um conjunto fechado;
(iii) Seja fFigni=1 uma coleção �nita de conjuntos fechados. Note que Mn (
Sn
i=1 Fi) =Tn
i=1 (MnFi). Sabemos queMnFi é aberto e, portanto, \ni=1 (MnFi) também o é. Isto agora
implica que o seu complemento,
Sn
i=1 Fi, é fechado. �
De�nição 1.5. Para todo conjunto A, chamamos de interior de A o maior conjunto aberto
contido em A. Isto é,
int(A) = Ao :=
S
fI � A : I abertog:
De�nição 1.6. Para todo conjunto A, o fecho de A é o menor conjunto fechado que contém
A. Isto é,
cl(A) = A :=
\
fF � A : F fechadog:
De�nição 1.7. Uma sequência (xm) converge para um ponto x 2 M se, para todo " > 0,
existe k 2N tal que xm 2 B(x; ");8m � k. Neste caso, também escrevemos que
lim
m!1
xm = x ou limxm = x ou xm ! x:
Teorema 1.3. Em qualquer espaço métrico (M;d), as seguintes a�rmações são equivalentes:
(i) A �M é um conjunto fechado;
(ii) Para toda sequência convergente (xm) 2 A1, limxm 2 A.
Demonstração. (i) =) (ii) Seja A � M um conjunto fechado, então MnA é aberto.
Considere uma sequência convergente (xm) 2 A1 e de�na x := limxm. Suponha, por
absurdo, que x 2MnA. Por hipótese, MnA é aberto, o que implica que existe � > 0 tal que
B(x; �) � MnA. Como fxmg � A, fxmg \ B(x; �) = ?. Isso implica que @k 2 N tal que
xm 2 B(x; �);8m � k, o que contradiz o pressuposto de que xm ! x.
(ii) =) (i) Suponha, agora, que A não seja fechado. Isto é, 9x 2 MnA tal que 8� > 0,
B(x; �) \ A 6= ?. Isto implica que, pra todo N , nós podemos encontrar xm 2 B(x; 1
m
) \ A.
Observe agora que xm ! x =2 A, o que contradiz (ii). �
1.1 Métrica Relativa
Suponha que (M;d) seja um espaço métrico, e A �M . Nós podemos pensar em (A; d) como
um espaço métrico. Nós dizemos que (A; d) é um subespaço métrico de (M;d).
Note que a bola aberta de centro x e raio � em (A; d) é dada por
BA(x; �) = fy 2 A : d(x; y) < �g = BM(x; �) \ A:
Teorema 1.4. Seja (A; d) um subespaço métrico de (M;d). Então:
6 CAPÍTULO 1. ESPAÇOS MÉTRICOS
(i) Um conjunto I é aberto em (A; d) se, e somente se, existe um conjunto V aberto em
(M;d) tal que I = V \ A;
(ii) Um conjunto F é fechado em (A; d) se, e somente se, existe um conjunto C fechado
em (M;d) tal que F = C \ A.
Demonstração. (i) Suponha primeiro que I é aberto em (A; d). Isto é, 8x 2 I, existe �x > 0
tal que BA(x; �x) � I. Note que
I =
S
x2I
BA(x; �x)
=
S
x2I
BM(x; �x) \ A
= A \
�S
x2I
BM(x; �x)
�
:
Agora observe que, pelo Teorema 1.1, [x2IBM(x; �x) é aberto em (M;d).
Suponha agora que existe V aberto em (M;d) tal que I = V \A. Pegue x 2 I � V . Como
V é aberto, existe � > 0 tal que BM(x; �) � V . Isso implica que BM(x; �) \A � V \A = I.
Como BA(x; �) = BM(x; �) \ A e x foi escolhido arbitrariamente, nós concluímos que I é
aberto em (A; d).
(ii) Suponha que F seja fechado em (A; d). Isto é, AnF é aberto em (A; d). Pela parte
(i), existe V aberto em (M;d) tal que AnF = V \ A. De�na C :=MnV . Como V é aberto
em (M;d), C é fechado em (M;d). Note agora que C\A = (MnV )\A = (M\A)n(V \A) =
An(V \ A) = An(AnF ) = F .
Suponha agora que exista um conjunto C fechado em (M;d) tal que F = A \ C. De�na
V := M n C. Como C é fechado em (M;d), V é aberto em (M;d). Pela parte (i), V \ A é
aberto em (A; d). Note agora que V \A = (M nC)\A = (M \A)n (C \A) = An (C \A) =
A nF . Ou seja, A nF é um conjunto aberto em (A; d) e, consequentemente, F é fechado em
(A; d). �
1.2 Exercícios
Exercício 1.2. Seja (xm) uma sequência qualquer em R. Mostre que (xm) tem uma subsequência
monótona.1.1
Exercício 1.3. Seja (xm) uma sequência limitada em R.1.2 Mostre que (xm) tem uma
subsequência convergente.
Exercício 1.4. Seja (xm) uma sequência em Rn. Então xm ! x se, e somente se, xmi ! xi,
8i = 1; 2; :::; n.
Exercício 1.5. Seja (M;d) um espaço métrico e �xe x 2 M . Nós dizemos que N(x) � M
é uma vizinhança de x se existe � > 0 tal que B(x; �) � N(x). Mostre que O � M é aberto
se e somente se pra todo x 2 O existe uma vizinhança N(x) de x tal que N(x) � O.
1.1Isto é, existe uma subsequência (xmk) de (xm) tal que xmk+1 � xmk pra todo k 2 N ou xmk+1 � xmk
pra todo k 2 N.
1.2Isto é, existem a; b 2 R tais que a � xm � b pra todo m 2 N.
1.2. EXERCÍCIOS 7
Exercício 1.6. Seja (M;d) um espaço métrico e suponha que O �M é um conjunto aberto
e F �M é um conjunto fechado. Mostre que
(i) O n F := fx 2 O : x =2 Fg é um conjunto aberto;
(ii) F nO := fx 2 F : x =2 Og é um conjunto fechado.
Exercício 1.7. Mostre que as suas conclusões mudariam no exercício acima se F fosse
aberto ou se O fosse fechado. Isto é, dê um exemplo de dois conjuntos abertos O e F tais
que O n F não é aberto, e dê um exemplo de dois conjuntos fechados O e F tais que F n O
não é fechado.
Exercício 1.8. Seja (M;d) um espaço métrico e seja A um subconjunto de M . Nós dizemos
que x 2 A é um ponto interior se existe � > 0 tal que B(x; �) � A. Nós dizemos que x é
um ponto de fecho de A se existe sequência (xm) tal que fxmg � A e xm ! x. Mostre que
int(A) = fx 2 A : x é ponto interior de Ag e cl(A) = fx 2M : x é ponto de fecho de Ag.
8 CAPÍTULO 1. ESPAÇOS MÉTRICOS
Capítulo 2
Conjuntos Compactos
Seja (M;d) um espaço métrico e A � M . Dizemos que uma coleção de conjuntos B é uma
cobertura de A se A �
S
fB 2 Bg.
Se todos os conjuntos em B forem abertos, dizemos que B é uma cobertura aberta de A.
De�nição 2.1. Dizemos que A é um conjunto compacto se para toda cobertura aberta B
de A existe D � B, D �nito, tal que A �
S
fB 2 Dg. Em palavras, A é um conjunto
compacto se toda cobertura aberta de A tem uma subcobertura �nita que ainda cobre A.
Exemplo 2.1. (0; 1) não é compacto.
Para ver isto, de�na B := f(0 + �; 1 � �) : � 2 (0; 1
2
)g. Note que B é uma cobertura
aberta de (0; 1). No entanto, para qualquer D � B, D �nito,
S
fB 2 Dg = (0 + ��; 1� ��)
para algum �� 2 (0; 1
2
), o que certamente não cobre (0; 1).
Exemplo 2.2. Todo conjunto �nito é compacto.
Proposição 2.1. Seja A um conjunto compacto. Se B � A é fechado, então B é compacto.
Demonstração. Seja B uma cobertura aberta de B. Note que B[fMnBg é uma cobertura
aberta de A, pois, por hipótese, B é fechado. Como A é compacto, 9D � B[fMnBg �nito
tal que A �
S
fC 2 Dg. Como B � A, �ca claro que DnfMnBg é uma subcobertura �nita
de B que ainda cobre B. �
De�nição 2.2. Dizemos que um conjunto A é limitado se existem x 2 M e � > 0 tais que
A � B(x; �).
Teorema 2.1. Todo conjunto compacto é fechado e limitado.
Demonstração. Suponha que A seja compacto e �xe x 2 M . Note que fB(x;m) : m 2 Ng
é uma cobertura aberta de A. Como A é compacto, isto implica que existe m� 2 N tal que
A � B(x;m�). Isto é, A é limitado.
Agora, �xe x 2 M n A. Note que fM n B(x; 1
m
) : m 2 Ng é uma cobertura aberta de A.
Como A é compacto, isto implica que existe m� 2 N tal que A � (M nB(x; 1
m� )). Mas então
B(x; 1
m� ) � M n A. Como x foi escolhido de forma arbitrária, nós concluímos que M n A é
um conjunto aberto e, consequentemente, A é fechado. �
9
10 CAPÍTULO 2. CONJUNTOS COMPACTOS
2.1 Compacticidade Sequencial
Seja (M;d) um espaço métrico e considere uma sequência qualquer (xm) 2 M1. Seja
m : N! N uma função estritamente crescente. De�na agora uma sequência (yk) 2M1 por
yk := xm(k) pra todo k 2 N. Nós dizemos que (yk) é uma subsequência de (xm) e usamos a
notação (xmk) para representar uma subsequência arbitrária de (xm).
Exercício 2.1. Seja (M;d) um espaço métrico. Mostre que se (xm) é uma sequência tal que
xm ! x 2M , então xmk ! x pra toda subsequência (xmk) de (xm).
De�nição 2.3. Dizemos que um conjunto é sequencialmente compacto se pra toda sequência
(xm) 2 A1 existem uma subsequência (xmk) de (xm) e x 2 A tais que xmk ! x.
Lema 2.1. Se A é sequencialmente compacto então, para qualquer " > 0, existe B � A, B
�nito, tal que A �
S
fB(x; ") : x 2 Bg.
Demonstração. Pegue um conjunto A sequencialmente compacto e suponha que exista " > 0
tal que, para todo B � A, B �nito, An (
S
fB(x; ") : x 2 Bg) 6= ?. Inicie com um elemento
x1 qualquer em A. Por hipótese, existe x2 2 AnB(x1; "). Prosseguindo indutivamente
nós podemos construir uma sequência (xm) 2 A1 tal que, para todo m 2 N, xm+1 2
An
Sm
i=1B(x
i; "). Isto implica que (xm) é uma sequencia tal que, 8k 6= l, d(xk; xl) � ". É
fácil veri�car que tal sequência não pode ter uma subsequência convergente. Para ver isto,
suponha que (xmk) seja uma subsequência de (xm) tal que xmk ! x. Isso implica que para
k̂ e k0 grandes o su�ciente, nós temos d(xmk̂ ; x) < "
2
e d(xmk0 ; x) < "
2
. Agora, a desigualdade
triangular nos dá
d(xmk̂ ; xmk0 ) � d(xmk̂ ; x) + d(x; xmk0 )
<
"
2
+
"
2
= ";
o que é uma contradição. Nós concluímos que (xm) não tem subsequencia convergente, o
que contradiz a compacticidade sequencial de A. Logo, a a�rmação no enunciadodo lema
tem que ser verdadeira. �
Lema 2.2. Suponha que A seja sequencialmente compacto e que I seja uma cobertura aberta
de A. Então existe " > 0 tal que, para todo x 2 A existe Ix 2 I com B(x; ") � Ix.
Demonstração. PegueA sequencialmente compacto e uma cobertura aberta I deA. Suponha
que para todo " > 0 exista x 2 A tal que B(x; ")nI 6= ?, para todo I 2 I. Então, para
cada m 2 N, nós podemos encontrar xm 2 A tal que B(xm; 1
m
)nI 6= ? para todo I 2 I.
Como A é sequencialmente compacto, existe x� 2 A e subsequência (xmk) de (xm) tal que
xmk ! x�. Como x� 2 A, 9I� 2 I tal que x� 2 I�. Já que I� é aberto, existe " > 0 tal que
B(x�; ") � I�. Seja k grande o su�ciente tal que d(xmk ; x�) < "
2
e 1
mk
< "
2
. Note agora que
para todo y 2 B(xmk ; 1
mk
) nós temos:
d(y; x�) � d(y; xmk) + d(xmk ; x�)
<
"
2
+
"
2
= ":
Assim, B(xmk ; 1
k
) � B(x�; ") � I�, o que contradiz a forma com que escolhemos os termos
da sequência (xm). Nós concluímos que o lema é verdadeiro. �
2.1. COMPACTICIDADE SEQUENCIAL 11
Teorema 2.2 (Caracterização Sequencial de Conjuntos Compactos). Seja (M;d) um espaço
métrico. Um conjunto A �M é compacto se, e somente se, é sequencialmente compacto.
Demonstração. Suponha primeiro que A seja um conjunto compacto. Suponha também que
(xm) 2 A1 não tenha nenhuma subsequência que convirja para algum elemento de A. Como
A é fechado, isto implica que (xm) não tem nenhuma subsequência convergente em (M;d).
Nós precisamos da seguinte a�rmação:
A�rmação 1. fxmg é um conjunto fechado.
Demonstração da A�rmação. Pegue y 2Mnfxmg e suponha que, para todo " > 0, B(y; ")\
fxmg 6= ?. Para k = 1, pegue xm1 2 fxmg \ B(y; 1). Tome xm2 2 fxmg \ B(y; 1
2
) tal que
m2 > m1. Para ver que isto é possível, de�na � := minm=1;:::;m1 d(x
m; y). Por hipótese, fxmg\
B(y; �)\B(y; 1
2
) 6= ?. Podemos então pegar xm2 2 fxmg\B(y; �)\B(y; 1
2
). Garantidamente,
m1 < m2. Procedendo indutivamente desta forma, nós obtemos uma subsequência (xmk) de
(xm) tal que, para todo k, d(xmk ; y) < 1
k
. Ou seja, xmk ! y. Mas isto contradiz a hipótese
de que (xm) não tem nenhuma subsequência convergente. Nós concluímos, portanto, que
fxmg é um conjunto fechado. k
Como fxmg � A é fechado, a proposição 2.1 garante que fxmg é compacto. Sem perda de
generalidade, nós podemos assumir que todos os elementos de (xm) são distintos. Precisamos,
agora, da seguinte a�rmação:
A�rmação 2. 8y 2 fxmg, existe "y > 0 tal que B(y; "y) \ fxmg = fyg.
Demonstração da A�rmação. Para provar a a�rmação, �xe y 2 fxmg. Como (xm) não tem
nenhuma subsequência convergente, 9" > 0 tal que B(y; ") tem �nitos elementos. De�na
"y := minfd(x; y) : x 2 fB(y; ") \ fxmgg n fygg:
Note que B(y; "y) \ fxmg = fyg: k
Finalmente, note que fB(y; "y) : y 2 fxmgg é uma cobertura aberta de fxmg que
claramente não tem uma subcobertura �nita que ainda cubra fxmg. Isto contradiz o fato de
que fxmg é compacto. Nós concluímos que toda sequência (xm) tal que fxmg � A tem uma
subsequência (xmk) tal que xmk ! x 2 A. Isto é, A é sequencialmente compacto.
Assuma, agora, que A seja sequencialmente compacto e pegue uma cobertura aberta I
de A. Pelo Lema 2.2, existe " > 0 tal que 8x 2 A, existe Ix 2 I com B(x; ") � Ix. Pelo
Lema 2.1, existe B � A, B �nito, tal que A �
S
fB(x; ") : x 2 Bg. Mas então, é claro que
fIx : x 2 Bg é uma subcobertura �nita de I que ainda cobre A, portanto A é compacto. �
Nós precisamos agora do seguinte lema:
Lema 2.3. Pra qualquer � > 0, [��; �]n é compacto em Rn.
Demonstração. Pegue (xm) tal que fxmg � [��; �]n. Como (xm1 ) é uma sequência limitada,
existe subsequência (xmk) de (xm) tal que (xmk1 ) converge. Como (x
mk
2 ) é limitada, existe
subsequência de (xmk), que novamente chamaremos de (xmk), tal que (xmk1 ) e (x
mk
2 ) ambas
convergem. Prosseguindo desse modo, nós obtemos uma subsequência (xmk) que converge em
todas as coordenadas. Pelo Exercício 1.4, (xmk) converge em Rn. Como [��; �]n é fechado,
limk!1 x
mk 2 [��; �]n. Ou seja, [��; �]n é sequencialmente compacto. �
12 CAPÍTULO 2. CONJUNTOS COMPACTOS
O lema acima implica que no Rn ser compacto equivale a ser fechado e limitado.
Teorema 2.3. Em Rn, um conjunto A é compacto se, e somente se, A é fechado e limitado.
Demonstração. Suponha que A seja fechado e limitado. Então, 9� > 0 tal que A � [��; �]n.
Como A é fechado e já mostramos que subconjuntos fechados de conjuntos compactos são
compactos (Proposição 2.1 ), A é compacto. A outra direção segue do Teorema 2.1. �
2.2 Exercícios
Exercício 2.2. Seja (M;d) um espaço métrico. Nós dizemos que uma coleção A de conjuntos
tem a propriedade das interseções �nitas se \B 6= ; pra qualquer subcoleção �nita de A.
Mostre que A �M é um conjunto compacto se e somente se pra toda coleção A de conjuntos
tal que B � A e B é fechado em (A; d) pra todo B 2 A, e além disto A tem a propriedade
das interseções �nitas nós temos \A 6= ;.
Exercício 2.3. Seja (M;d) um espaço métrico e considere uma coleção A de conjuntos
compactos em (M;d). Mostre que \A é um conjunto compacto.
Exercício 2.4. Seja (M;d) um espaço métrico e seja (Am) uma sequência de conjuntos
compactos e não vazios em (M;d) tal que, pra todo m 2 N, Am+1 � Am. Mostre que
\1m=1Am 6= ;.
Capítulo 3
Continuidade
De�nição 3.1. Sejam X e Y dois espaços métricos. Dizemos que a função f : X ! Y é
contínua em x 2 X se, 8", 9� > 0 tal que se dX(x; y) < �, então dY (f(x); f(y)) < ". Isto
é, se para todo " > 0 existe � > 0 tal que f(BX(x; �)) � BY (f(x); "). Se f é contínua em
todos os pontos de X, dizemos simplesmente que f é contínua.
Exemplo 3.1. f : R! R de�nida por
f(x) :=
�
0; se x � 0
1; se x > 0
não é contínua em 0. Note que para qualquer � > 0 existe y 2 B(0; �) com f(y) = 1. Isto
implica que pra " = 1=2, por exemplo, não é verdade que f(BX(0; �)) � BY (f(0); ") pra
nenhum � > 0.
Teorema 3.1. Seja f : X ! Y . As seguintes a�rmações são equivalentes:
(i) f é contínua;
(ii) Para todo conjunto I aberto em Y , f�1(I) := fx 2 X : f(x) 2 Ig é aberto;
(iii) Para todo conjunto F fechado em Y , f�1(F ) é fechado;
(iv) Para toda sequência convergente xm ! x nós temos f(xm)! f(x).
Demonstração. (i) =) (iv) Fixe " > 0 qualquer. Como f é contínua, existe � > 0 tal
que f(BX(x; �)) � BY (f(x); "). Como xm ! x, existe k 2 N tal que m � k implica
que xm 2 BX(x; �). Mas então, para m � k, como f(BX(x; �)) � BY (f(x); "), nós temos
f(xm) 2 B(f(x); "). Como isto vale para qualquer " > 0, nós concluímos que f(xm)! f(x).
(iv) =) (iii) Seja F � Y um conjunto fechado. Queremos mostrar que f�1(F ) é fechado.
Para isto, pegue qualquer sequência convergente (xm) tal que fxmg 2 f�1(F ). Precisamos
mostrar que x := lim xm 2 f�1(F ). Por (iv), xm ! x implica que f(xm)! f(x). Como F é
fechado, isto implica que f(x) 2 F (Teorema 1.3). Mas então x 2 f�1(F ) e nós concluímos
que f�1(F ) é fechado, pelo Teorema 1.3.
(iii) =) (ii) Fixe um conjunto aberto qualquer I � Y . De�na o conjunto F := Y nI.
Decorre da de�nição de conjunto fechado que F é fechado. Por (iii), temos que f�1(F )
13
14 CAPÍTULO 3. CONTINUIDADE
também é fechado e, consequentemente, X nf�1(F ) é aberto. Mas observe que Xnf�1(F ) =
fx 2 X : f(x) =2 Fg = fx 2 X : f(x) 2 Ig = f�1(I).
(ii) =) (i) Fixe x 2 X e " > 0. Como BY (f(x); ") é um conjunto aberto, (ii) implica
que f�1(BY (f(x); ")) é aberto em X. Como x 2 f�1(BY (f(x); ")), existe � > 0 tal que
B(x; �) � f�1(BY (f(x); ")), o que implica que f(BX(x; �)) � BY (f(x); "). �
Observação 3.1. A imagem de um conjunto aberto (fechado) não necessariamente é um
conjunto aberto (fechado), mesmo para funções contínuas. Por exemplo, se f : R ! R é
de�nida por f(x) = 0 se x 2 [0; 1], f(x) = x � 1 se x > 1, e f(x) = x se x < 0, então f é
contínua, mas f((0; 1)) = f0g, que não é um conjunto aberto.
3.1 Continuidade e Compacticidade
Proposição 3.1. Sejam X e Y espaços métricos. Se f : X ! Y é contínua e A � X é
compacto, então f(A) é compacto.
Demonstração. Seja I uma cobertura aberta de f(A). Como f é contínua, para cada I 2 I,
f�1(I) é aberto em X. Mas então, ff�1(I) : I 2 Igé uma cobertura aberta de A. Como
A é compacto, existe V � I, V �nito, tal que A �
S
ff�1(I) : I 2 Vg. Note que V é uma
subcobertura �nita de I tal que f(A) �
S
fI 2 Vg. Ou seja, f(A) é compacto.
Alternativamente, nós também podemos demonstrar o resultado utilizando compacticidade
sequencial. Para isto, pegue (ym) tal que fymg � f(A). Para cada ym, pegue xm 2 A tal que
f(xm) = ym. Como A é compacto, existe subsequência (xmk) de (xm) tal que xmk ! x 2 A.
Como f é contínua, isto implica que f(xmk) = ymk ! f(x). Isto mostra que f(A) é
compacto. �
Corolario 3.1 (Teorema de Weierstrass). Seja X um espaço métrico e f : X ! R contínua.
Se A é compacto, então existem x; y 2 A tais que f(x) � f(z) e f(z) � f(y), 8z 2 A.
Demonstração. Da proposição anterior, f(A) é um conjunto fechado e limitado em R. Então,
sup f(A) 2 f(A) e inf f(A) 2 f(A). �
3.2 Continuidade Uniforme
De�nição 3.2. Dizemos que f : X ! Y é uniformemente contínua se, para todo " > 0,
existe � > 0 tal que, para todo x 2 X, f(BX(x; �)) � BY (f(x); "). Equivalentemente,
f : X ! Y é uniformemente contínua se, para todo " > 0, existe � > 0 tal que, pra todo
x; y 2 X, dX(x; y) < � implica que dY (f(x); f(y)) < ".
Exemplo 3.2. f(x) = 1
x
é contínua em (0;1), mas não é uniformemente contínua.
Proposição 3.2. Se X é compacto e f : X ! Y é contínua, então f é uniformemente
contínua.
3.3. EXERCÍCIOS 15
Demonstração. Fixe " > 0. Note que fBY (f(x); ") : x 2 Xg é uma cobertura aberta de
f(X). Para cada x 2 X, f�1(BY (f(x); "2)) é aberto, o que implica que existe �x > 0 tal
que f(BX(x; �x)) � BY (f(x); "2). Obviamente, fBX(x;
�x
2
) : x 2 Xg é uma cobertura aberta
de X. Como X é compacto, existem x1; :::; xn 2 X tais que X �
Sn
i=1BX(xi;
�i
2
). De�na
� := 1
2
minf�1; :::; �ng. Agora pegue quaisquer x e y em X, com dX(x; y) < �. Claramente
existe xi tal que x 2 BX(xi; �i2 ). Mas então,
dX(xi; y) � dX(xi; x) + dX(x; y)
<
�i
2
+ �
� 2�i
2
= �i:
Ou seja, fx; yg � BX(xi; �i). Isto implica que dY (f(xi); f(x)) < "2 e dY (f(xi); f(y)) <
"
2
.
Mas então,
dY (f(x); f(y)) � dY (f(xi); f(x)) + dY (f(xi); f(y))
<
"
2
+
"
2
= ":
Como x e y foram escolhidos arbitrariamente, isto mostra que f é uniformemente contínua
em X. �
3.3 Exercícios
Exercício 3.1. Sejam X, Y e Z espaços métricos e suponha que f : X ! Y e g : f(X)! Z
sejam funções contínuas.3.1 Mostre que h : X ! Z de�nida por h := g � f (isto é, pra todo
x 2 X, h(x) := g(f(x))) é uma função contínua.
Exercício 3.2. Mostre que a função f : Rn ! R de�nida por f(x) := kxk, pra todo x 2 Rn
é contínua.3.2 Dica: na verdade é mais fácil demonstrar um resultado mais geral. Mostre
que, em qualquer espaço métrico X e para qualquer ponto x� 2 X, a função de�nida por
f(x) := dX(x; x
�) é contínua.
Exercício 3.3. Nós dizemos que um conjunto A em um espaço métrico X é totalmente
limitado se pra todo " > 0 existe um subconjunto �nito B de A tal que A � [fBX(x; ") :
x 2 Bg. Suponha agora que X e Y sejam dois espaços métricos e que f : X ! Y seja
uma função uniformemente contínua tal que f(X) = Y . Mostre que se X é totalmente
limitado, então Y também é totalmente limitado. Dê um exemplo mostrando que isto não é
necessariamente verdade quando f é apenas contínua.
3.1Aqui estamos pensando em f(X) como um subespaço métrico de Y , é claro.
3.2Aqui você pode escolher qualquer uma das normas em Rn. Por exemplo, kxk =
pPn
i=1 x
2
i .
16 CAPÍTULO 3. CONTINUIDADE
Capítulo 4
Correspondências
De�nition 4.1. Sejam X e Y espaços métricos. Dizemos que � é uma correspondência de
X até Y , � : X � Y , se � é uma função que leva de X até 2Y nf?g. Isto é, para cada x 2 X,
�(x) é um subconjunto não vazio de Y .
Exemplo 4.1. Seja p 2 Rn++ e l 2 R++, nós de�nimos a correspondência orçamentária
B(p; l) por
B(p; l) :=
(
x 2 Rn+ :
nX
i=1
pixi � l
)
:
4.1 Continuidade de Correspondências
4.1.1 Hemicontinuidade Superior
De�nição 4.1. Dizemos que � : X � Y é hemicontínua superior (HCS) em x 2 X se, para
todo I � Y aberto tal que �(x) � I, existe � > 0 tal que �(y) � I sempre que dX(x; y) < �.
Se � é HCS para todo x 2 S � X, dizemos que � é HCS em S
Intuitivamente, � não é hemicontínua superior em x se pequenos desvios de x fazem com
que �(x) cresça bruscamente. Por exemplo, a correspondência da esquerda na �gura 4.1 não
é HCS em x nem em y, já a da direita é HCS em todo o seu domínio.
Figura 4.1: Correspondências.
17
18 CAPÍTULO 4. CORRESPONDÊNCIAS
Proposição 4.1 (Caracterização Sequencial de Hemicontinuidade Superior). Sejam X e Y
espaços métricos e � : X � Y uma correspondência. �(x) é compacto e � é HCS em x se, e
somente se, para todo par de sequências (xm); (ym) 2 X1�Y 1 com xm ! x e ym 2 �(xm),
8m, existe subsequência (ymk) de (ym) tal que ymk ! y 2 �(x).4.1
Demonstração. Suponha primeiro que para todo par de sequências (xm) 2 X1 e (ym) 2 Y 1
com xm ! x e ym 2 �(xm) para todo m 2 N nós consigamos achar uma subsequência (ymk)
de (ym) com ymk ! y 2 �(x). Vamos mostrar primeiro que �(x) é compacto. Pegue (ym)
tal que fymg � �(x). De�na (xm) por xm = x, 8m. Obviamente, xm ! x e ym 2 �(xm),
8m. A propriedade no enunciado implica que existe subsequência (ymk) de (ym) tal que
ymk ! y 2 �(x). Isso mostra que �(x) é sequencialmente compacto e, portanto, é compacto.
Vamos mostrar agora que �(x) é HCS em x. Suponha que � não seja HCS em x.
Ou seja, existe I aberto com �(x) � I tal que, para todo � > 0, existe x̂ 2 BX(x; �)
com �(x̂)nI 6= ?. Isso implica que, 8m 2 N, existem xm 2 BX(x; 1m) e y
m 2 �(xm)nI.
Claramente, xm ! x. No entanto, como Y nI é fechado, qualquer subsequência convergente
de (ym) tem que convergir para um ponto y 2 Y nI. Isto contradiz a propriedade no enunciado
e, consequentemente, nós concluímos que � é HCS.
Suponha agora que �(x) seja compacto e � seja HCS em x. Pegue sequências (xm) 2 X1
e (ym) 2 Y 1 tais que xm ! x e ym 2 �(xm), 8m. Para cada k 2 N, de�na Ik :=
S
fBY (ŷ; 1k ) :
ŷ 2 �(x)g. Note que, pra todo k, Ik é aberto e �(x) � Ik. Como xm ! x e � é HCS em
x, existe xmk tal que �(xmk) � Ik. Além disto, é possível escolher os mk�s tais que k0 > k
se, e somente se, mk0 > mk. Isto nos permite encontrar, para cada k, ŷk 2 �(x) com
d(ymk ; ŷk) < 1
k
. Como �(x) é compacto, (ŷk) tem uma subsequência convergente, (ŷkj). Isto
é, ŷkj ! y 2 �(x). Agora, �xe " > 0. Como ŷkj ! y, existe J tal que, para todo j � J ,
dY (ŷ
kj ; y) < "
2
e dY (y
mkj ; ŷkj) < "
2
. Mas então, para j � J ,
dY (y
mkj ; y) � dY (ymkj ; ŷkj) + dY (ŷkj ; y)
<
"
2
+
"
2
= ":
Ou seja, ymkj ! y: �
Exemplo 4.2. B : Rn+1++ � Rn+ de�nida por
B(p; l) := fx 2 Rn+ : p � x � lg
é HCS. Para ver isto, suponha que (pm; lm)! (p; l) e que (xm) seja tal que xm 2 B(pm; lm),
8m. Precisamos mostrar que existe subsequência (xmk) de (xm) com xmk ! x 2 B(p; l). Para
i = 1; :::; n, de�na p�i := inffpmi : m = 1; 2; :::g. Como pmi ! pi > 0, sabemos que p�i > 0
(Demonstração?). Similarmente, de�na l� := supflm : m = 1; 2; :::g. Como lm ! l 2 R++,
sabemos que l� < 1. Note que, 8m 2 N, B(pm; lm) � B(p�; l�). Isto implica que, para
todo m 2 N, B(pm; lm) � B(p�; l�). Como B(p�; l�) é um conjunto compacto, nós sabemos
que existe subsequência (xmk) de (xm) tal que xmk ! x 2 B(p�; l�). Lembre agora que, 8k,
pmk � xmk � lmk . Como pmk ! p, xmk ! x e lmk ! l, isto implica que p � x � l. Usando a
caracterização sequencial para correspondências HCS, nós concluímos que B é HCS.
4.1Esta é uma versão corrigida da proposição E.2 em Ok (2007). O enunciado da proposição em Ok (2007)
está incorreto.
4.1. CONTINUIDADE DE CORRESPONDÊNCIAS 19
4.1.2 Hemicontinuidade Inferior
De�nição 4.2. Dizemos que � : X � Y é hemicontínua inferior (HCI) em x se, para todo
I aberto tal que �(x) \ I 6= ?, 9� > 0 tal que dX(x; y) < � implica que �(y) \ I 6= ?. Se �
é HCI para todo x 2 S � X, dizemos que � é HCI em S.
Intuitivamente, o empecilho para que � seja HCI são as implosões. Isto é, quando
pequenas perturbações em x fazem �(x) encolher abruptamente. Por exemplo, a correspondência
da esquerda na �gura 4.1 é HCI em todo o seu domínio,já a da direita não é HCI em x nem
em y.
Proposição 4.2 (Caracterização Sequencial de Hemicontinuidade Inferior). Sejam X e Y
dois espaços métricos. � é HCI em x 2 X se, e somente se, para toda sequência xm ! x e
todo y 2 �(x), existe (ym) tal que ym ! y e ym 2 �(xm), 8m.
Demonstração. Suponha primeiro que � seja HCI em x 2 X. Pegue (xm) tal que xm ! x
e y 2 �(x). Para cada m, se �(xm) \ BY (y; 1m) 6= ?, pegue y
m 2 �(xm) \ BY (y; 1m).
Se �(xm) \ BY (y; 1m) = ?, mas �(x
m) \ BY (y; 1k ) 6= ? para algum k 2 N, pegue y
m 2
�(xm) \ BY (y; 1k� ), em que k
� = maxfk 2 N : �(xm) \ BY (y; 1k ) 6= ?g. Finalmente, se
�(xm) \ BY (y; 1k ) = ? para todo k 2 N, pegue qualquer y
m 2 �(xm). Agora, �xe " > 0 e
k̂ 2 N tal que 1
k̂
< ". Como � é HCI em x, existe � > 0 tal que �(x0) \ BY (y; 1k̂ ) 6= ? para
todo x0 2 BX(x; �).
Como xm ! x, existe M > k̂ tal que xm 2 BX(x; �), 8m � M . Dada a construção da
sequência (ym), isto implica que, para todo m � M , nós temos ym 2 BY (y; 1k̂ ) � BY (y; ").
Como " foi escolhido arbitrariamente, isto mostra que ym ! y.
Suponha agora que � não seja HCI em x. Então existe I aberto tal que �(x) \ I 6= ?,
mas para todo � > 0, existe x0 2 B(x; �) com �(x0) \ I = ?. Fixe y 2 �(x) \ I. Para cada
m 2 N, pegue xm 2 BX(x; 1m) tal que �(x
m) \ I = ?. Agora, para cada m 2 N, pegue
qualquer ym 2 �(xm). Claramente, não pode ser verdade que ym ! y. �
Exemplo 4.3. B : Rn+1++ � Rn+ de�nida por
B(p; l) := fx 2 Rn+ : p � x � lg
é HCI. Para ver isto, suponha que (pm; lm) ! (p; l) e que x 2 B(p; l). Se p � x < l, então
existe M 2 N tal que pm � x < lm pra todo m � M . Escolhendo, então, uma sequência
Pra cada m 2 N, se x 2 B(pm; lm), de�na xm := x. Se x =2 B(pm; lm), o que implica que
pm � x > 0, de�na xm :=
�
lm
pm�x
�
x. Se p � x < l, então existe M 2 N tal que pm � x < lm
pra todo m � M . Escolhendo, então, uma sequência (xm) tal que xm é qualquer elemento
de B(pm; lm) se m < M e xm = x se m � M nós obtemos que xm ! x. Suponha agora
que p � x = l. Pra cada m, de�na �m := lm
pm�x . Note que, como (p
m; lm) ! (p; l) e p � x = l,
�m ! 1. Além disto, pm � (�mx) = lm pra todo m. Ou seja, pra todo m 2 N, nós temos
�mx 2 B(pm; lm). De�na, então, pra cada m 2 N, xm := �mx. Nós já argumentamos que
xm 2 B(pm; lm) pra todo m. Também é fácil ver que xm ! x.
Embora o argumento usado no exemplo 4.3 ilustre bem o uso da Proposição 4.2, uma
demonstração usando diratemente a de�nição de hemicontinuidade inferior pode ser até mais
simples.
20 CAPÍTULO 4. CORRESPONDÊNCIAS
Exercício 4.1. Mostre que B : Rn+1++ � Rn+ de�nida por
B(p; l) := fx 2 Rn+ : p � x � lg
é HCI usando diretamente a de�nição original de hemicontinuidade inferior.
4.1.3 Correspondências de Grá�co Fechado
De�nição 4.3. Dizemos que � : X � Y é fechada em x 2 X se, para todo (xm) 2 X1 e
(ym) 2 Y 1 com xm ! x, ym ! y e ym 2 �(xm), 8m, nós temos y 2 �(x). Se � é fechada
em todo x 2 X, dizemos que � tem grá�co fechado.
Proposição 4.3. Seja � : X � Y uma correspondência. Então:
(i) Se � é fechada em x 2 X e Y é compacto, então � é HCS em x e �(x) é compacto;
(ii) Se � é HCS em x 2 X e �(x) é um conjunto fechado, então � é fechada em x.
Antes de demonstrar a proposição, vamos mostrar que ser HCS e ter grá�co fechado não
são equivalentes, em geral.
Exemplo 4.4. A correspondência f : R� R de�nida por f(x) = f 1
x
g se x 6= 0 e f(0) = f0g
tem grá�co fechado mas não é HCS em 0. Note que sempre que xm ! 0 e fymg = f(xm) pra
todo m, nós temos ym ! 1, o que faz com que f seja de grá�co fechado em x (ver �gura
4.2). É fácil ver que f não é hemicontínua superior nem inferior em 0.
Figura 4.2: Função com grá�co fechado, mas discontínua em 0
Exemplo 4.5. � : R� R de�nida por �(x) := (0; 1] 8x 2 R é HCS em todo o domínio, mas
não tem grá�co fechado em nenhum ponto. Note que, para qualquer x 2 R, nós podemos
de�nir xm := x pra todo m 2 N e ym := 1
m
. Claramente xm ! x, ym 2 �(xm) pra todo m,
mas ym ! 0 =2 �(x).
4.2. TEOREMA DO MÁXIMO 21
Demonstração da Proposição 4.3. (i) Pegue xm ! x e (ym) 2 �(xm), 8m. Como Y é
compacto, existe uma subsequência (ymk) de (ym) tal que ymk ! y 2 Y . Como xmk ! x,
ymk ! y, ymk 2 �(xmk) 8k e � é fechada em x, isto implica que y 2 �(x). Usando a
caracterização sequencial de HCS, nós aprendemos que � é HCS em x e �(x) é compacto.
(ii) Exercício 4.2. �
Exercício 4.2. Sejam X e Y espaços métricos e � : X � Y uma correspondência. Mostre
que se � é hemicontínua superior em x 2 X e �(x) é um conjunto fechado, então � é fechada
em x. Dica: pegue sequências convergentes (xm) e (ym) com xm ! x e ym 2 �(xm) pra todo
m 2 N. Repetindo o raciocínio usado na segunda parte da demonstração da caracterização
de hemicontinuidade superior usando sequências é possível construir uma subsequência (ymk)
de (ym) e uma sequência (ŷmk) tal que fŷmkg � �(x) e, pra todo k 2 N, dY (ymk ; ŷmk) < 1=k.
Complete a demonstração observando que lim ymk = lim ŷmk e usando o fato de que �(x) é
um conjunto fechado.
4.2 Teorema do Máximo
Teorema 4.1 (Teorema do Máximo de Berge). Sejam � e X dois espaços métricos, � :
�� X uma correspondência de valores compactos e contínua e � : ��X ! R uma função
contínua. De�na:
�(�) := argmaxf�(�; x) : x 2 �(�)g
e
��(�) := maxf�(�; x) : x 2 �(�)g:
Então:
(i) � é de valores compactos, hemicontínua superior e de grá�co fechado;
(ii) �� é contínua.
Demonstração. (i) Como � é de valores compactos e �(�; �) é contínua, � e �� estão bem
de�nidos. Fixe � 2 � e sequências (�m) e (xm) tais que �m ! � e xm 2 �(�m) 8m. Queremos
encontrar uma subsequência (xmk) de (xm) tal que xmk ! x 2 �(�). Pegue x 2 �(�) � �(�).
Como � é HCI, existe sequência (x̂m) tal que x̂m ! x e x̂m 2 �(�m) para todom. Além disto,
como � é HCS e �(�) é compacto, existe subsequência xmk de (xm) tal que xmk ! x� 2 �(�).
Como � é uma função contínua, xmk ! x�, x̂mk ! x e �(�mk ; xmk) � �(�mk ; x̂mk) 8k, nós
concluímos que �(�; x�) � �(�; x). Como x 2 �(�), isto implica que x� 2 �(�). Isto mostra
que � é HCS em � e �(�) é compacto. Pela Proposição 4.3, correspondências HCS e de
valores fechados têm grá�co fechado.
(ii) Vamos agora mostrar que �� é contínua. Para isto, pegue �m ! �. Precisamos
mostrar que ��(�m) ! ��(�). Fixe " > 0 e suponha que existam in�nitos termos de ��(�m)
tais que ��(�m) =2 (��(�)� "; ��(�)+ "). Isto implica que existe uma subsequência de ��(�m),
que chamaremos novamente de (��(�m)), tal que ��(�m) =2 (��(�) � "; ��(�) + ") 8m. Para
cada m, pegue xm 2 �(�m). Como � é HCS (pelo item (i) desta demonstração) e �(�) é
compacto, existe subsequência (xmk) de (xm) tal que xmk ! x 2 �(�). Como � é contínua,
��(�mk) = �(�mk ; xmk)! �(�; x) = ��(�):
22 CAPÍTULO 4. CORRESPONDÊNCIAS
Mas observe que isto é uma contradição, já que ��(�mk) =2 (��(�)� "; ��(�) + ") para todo k
implica que não pode ser verdade que ��(�mk)! ��(�). Nós concluímos que existem apenas
�nitos termos da sequência original ��(�m) tais que ��(�m) =2 (��(�)� "; ��(�) + "). Ou seja,
existe M 2 N tal que ��(�m) 2 (��(�) � "; ��(�) + ") 8m � M . Como " > 0 foi escolhido
arbitrariamente, isto mostra que ��(�m)! ��(�). �
Exemplo 4.6. Para (p; l) 2 Rn+1++ , de�na a correspondência de demanda Z : Rn+1++ � Rn+ e
a função de utilidade indireta v : Rn+1++ ! R por
v(p; l) := maxfu(x) : x 2 Rn+ e p � x � lg
e
Z(p; l) := argmaxfu(x) : x 2 Rn+ e p � x � lg,
em que u : Rn+ ! R é uma função contínua. Para cada (p; l) 2 Rn+1++ , de�na
B(p; l) := fx 2 Rn+ : p � x � lg:
Lembre-se que nós chamamos B de correspondência orçamentária. Note que podemos de�nir
v e Z como:
v(p; l) := maxfu(x) : x 2 B(p; l)g
e
Z(p; l) := argmaxfu(x) : x 2 B(p; l)g:
Como u é contínua e nós já vimos que B é contínua e de valores compactos, o teorema
do máximo se aplica e nós podemos concluir que v é uma função contínua e Z é uma
correspondência de valores compactos, HCS e de grá�co fechado.
4.3 Exercícios
Exercício 4.3. Sejam X e Y dois espaços métricos e suponha que � : X � Y seja uma
correpondência hemicontínua superior e de valores compactos (isto é, pra todo x 2 X, �(x)é um conjunto compacto). Mostre que se A � X é um conjunto compacto, então �(A) :=
fy 2 Y : y 2 �(x) pra algum x 2 Ag também é um conjunto compacto. Dica: em Ok (2007)
tem uma demonstração, mas tem uma demonstração mais simples usando sequências.
Exercício 4.4 (Caracterizações alternativas para hemicontinuidade superior e inferior).
Sejam X e Y espaços métricos e � : X � Y uma correspondência. Para qualquer conjunto
O � Y , de�na ��1(O) := fx 2 X : �(x) � Og e ��1(O) := fx 2 X : �(x) \ O 6= ;g.
Os conjuntos ��1(O) e ��1(O) são chamados de imagem inversa superior e inferior de O,
respectivamente. Mostre que � é hemicontínua superior se, e somente se, pra todo O aberto
em Y , ��1(O) é aberto em X, e � é hemicontínua inferior se, e somente se, pra todo O
aberto em Y , ��1(O) é aberto em X.
Exercício 4.5. Responda se as seguintes correspondências são hemicontínuas superior e
inferior. Demonstre a sua resposta para cada um dos casos.
4.3. EXERCÍCIOS 23
(a) � : R� R de�nida por �(x) := fy 2 R : �x2 � y � x2g;
(b) � : R� R de�nida por �(x) := fy 2 Z : y < xg;4.2
(c) � : R� R de�nida por �(x) := fy 2 Z : y � xg;
(d) � : R � R de�nida por �(x) := Q se x 2 R n Q e �(x) := R n Q se x 2 Q.4.3 Dica:
você precisará usar os fatos de que tanto o conjunto dos números racionais quanto o
conjunto dos números irracionais são densos em R. Isto é, qualquer subconjunto aberto
e não vazio de R inclui números racionais e números irracionais.
4.2Notação. O símbolo Z representa o conjunto dos números inteiros.
4.3Notação. O símboloQ representa o conjunto dos números racionais. Consequentemente, RnQ representa
o conjunto dos números irracionais.
24 CAPÍTULO 4. CORRESPONDÊNCIAS
Capítulo 5
Conjuntos Convexos
De�nição 5.1. Dizemos que A � Rn é um conjunto convexo se fx; yg � A e � 2 [0; 1]
implica que �x+ (1� �)y 2 A (ver �gura 5.1).
Figura 5.1: À esquerda um conjunto convexo e à direita um conjunto não convexo.
Lema 5.1. Se A e B são conjuntos convexos, então A \B é um conjunto convexo.
Demonstração. Pegue x; y 2 A \ B e � 2 [0; 1]. Como A é convexo, �x + (1 � �)y 2 A.
Como B é convexo, �x+ (1� �)y 2 B. Isto é, �x+ (1� �)y 2 A \B. �
A união de conjuntos convexos claramente não é necessariamente convexa.
Exemplo 5.1. f1g e f2g são conjuntos convexos, mas f1; 2g não é convexo.
A partir de agora, usaremos a seguinte notação.
Notação. Sejam A e B dois conjuntos quaisquer e �; 
 2 R. De�na:
�A+ 
B := f�x+ 
y : x 2 A e y 2 Bg:
Lema 5.2. Se A;B � Rn são convexos, então �A+ 
B é convexo 8�; 
 2 R.
Demonstração. Pegue x; y 2 �A+
B e � 2 [0; 1]. Como x; y 2 �A+
B, existem xA; yA 2 A
e xB; yB 2 B tais que x = �xA + 
xB e y = �yA + 
yB. Mas então,
�x+ (1� �)y = �(�xA + 
xB) + (1� �)(�yA + 
yB)
= �(�xA + (1� �)yA) + 
(�xB + (1� �)yB):
Como A e B são convexos, �xA + (1� �)yA 2 A e �xB + (1� �)yB 2 B, o que mostra que
�x+ (1� �)y 2 �A+ 
B. �
25
26 CAPÍTULO 5. CONJUNTOS CONVEXOS
Lema 5.3. Se A é convexo, então cl(A) é convexo.
Demonstração. Pegue x; y 2 cl(A) e � 2 [0; 1]. Isto implica que existem (xm) e (ym) com
fxmg; fymg � A e xm ! x, ym ! y. Como A é convexo, para cadam 2 N, �xm+(1��)ym 2
A. Como xm ! x e ym ! y, �xm + (1 � �)ym ! �x + (1 � �)y, o que implica que
�x+ (1� �)y 2 cl(A). �
Lema 5.4. Seja A um conjunto convexo com int(A) 6= ?. Se x 2 int(A) e y 2 cl(A), então
�x+ (1� �)y 2 int(A), 8� 2 (0; 1).
Demonstração. Suponha primeiro que y 2 A e �xe � 2 (0; 1). Como x 2 int(A), existe
� > 0 tal que B(x; �) � A. Vamos mostrar que B(�x+ (1� �)y; ��) � A. Para isto, pegue
w 2 B(�x+ (1� �)y; ��). De�na z := 1
�
w � (1��)
�
y. Observe que �z + (1� �)y = w. Falta
mostrar que z 2 A. Para isto, note que
kz � xk =




1�w � (1� �)� y � x



=




1�(w � (�x+ (1� �)y))



=
1
�
kw � (�x+ (1� �)y)k
<
1
�
(��) = �:
Ou seja, z 2 B(x; �) � A, o que mostra que w 2 A. Como a escolha de w foi arbitrária, nós
concluímos que B(�x+ (1� �)y; ��) � A e, consequentemente, �x+ (1� �)y 2 int(A).
Suponha agora que saibamos apenas que y 2 cl(A). Como x 2 int(A), existe � > 0 tal que
B(x; �) � A. Além disto, como y 2 cl(A), para qualquer 
 > 0 existe w 2 B(y; 
) \A. Seja

 := �
1��� e pegue w 2 B(y; 
)\A. De�na z := x�
(1��)
�
(w� y). Note que �z+(1��)w =
�x+ (1� �)y. Além disto,
kz � xk =




x� 1� �� (w � y)� x



=
1� �
�
kw � yk
<
1� �
�

 = �:
Ou seja, z 2 B(x; �) � int(A). Como z 2 int(A) e w 2 A, nós estamos no caso anterior, o
que implica que �x+ (1� �)y 2 int(A). �
O resultado acima tem os seguintes corolários:
Corolario 5.1. Se A é convexo, então int(A) é convexo.
Exercício 5.1. Mostre que se A é convexo e int(A) 6= ?, então cl(int(A)) = cl(A) e
int(cl(A)) = int(A).
27
De�nição 5.2. Para um conjunto A qualquer, de�na
K(A) :=
(
�1x1 + :::+ �nxn : n 2 N, x1; :::; xn 2 A, �1; :::; �n � 0 e
nX
i=1
�i = 1
)
:
Lema 5.5. Um conjunto A � Rn é convexo se, e somente se, A = K(A).
Demonstração. Suponha que A seja convexo e observer que é claro que A � K(A). Suponha
que todas as combinações convexas de n elementos de A estejam contidas em A (como A é
convexo, sabemos que isto é verdade para n = 1; 2). Suponha, então, que y = �1x1 + ::: +
�n+1xn+1, para �1; :::; �n+1 > 0 e x1; :::; xn+1 2 A. Note que
y = �n+1xn+1 + (1� �n+1)
�
�1
1� �n+1
x1 + :::+
�n
1� �n+1
xn
�
:
Pela hipótese de indução, �1
1��n+1x1 + :::+
�n
1��n+1xn 2 A e, portanto, y 2 A. Isto mostra que
K(A) � A e, consequentemente, A = K(A).
Suponha agora que A = K(A). Precisamos mostrar que K(A) é convexo. Pegue x; y 2
K(A). Por hipótese, existem �1; :::; �n � 0 com
Pn
i=1 �i = 1 e x1; :::; xn 2 A com x =
�1x1 + ::: + �nxn. Também existem 
1; :::; 
m � 0, com
Pm
j=1 
j = 1 e y1; :::; ym 2 A com
y = 
1y1 + :::+ 
mym. Mas então, para qualquer � 2 [0; 1],
�x+ (1� �)y = �
nX
i=1
�ixi + (1� �)
mX
j=1

jyj
Ou seja, �x+(1��)y também é uma combinação convexa de um número �nito de elementos
de A e, consequentemente, �x+ (1� �)y 2 K(A) = A. �
De�nição 5.3. Dado um conjunto A, de�nimos o fecho convexo de A, co(A), como sendo o
menor conjunto convexo que contém A. Isto é,
co(A) :=
\
fB convexo: A � Bg:
Teorema 5.1. Para todo conjunto A, co(A) = K(A).
Demonstração. Como já vimos que K(A) é convexo, sabemos que co(A) � K(A). Pegue
agora x 2 K(A). Isto implica que existem �1; :::; �m com
Pm
i=1 �i = 1 e x1; :::; xm 2 A
tais que
Pm
i=1 �ixi = x. Como A � co(A), sabemos que x1; :::; xm 2 co(A). Como co(A) é
convexo, isto implica que x =
Pm
i=1 �ixi 2 co(A), por um argumento análogo ao utilizado na
primeira parte da demonstração do Lema 5.5. �
Corolario 5.2. A é convexo se, e somente se, A = co(A).
Teorema 5.2 (Carathéodory). Seja A um subconjunto de Rn e x 2 co(A). Então, existem
�1; :::; �n+1 � 0 com
Pn+1
i=1 �i = 1 e x1; :::; xn+1 2 A tais que x = �1x1 + :::+ �n+1xn+1.
28 CAPÍTULO 5. CONJUNTOS CONVEXOS
Demonstração. Seja A um subconjunto de Rn e �xe x 2 co(A). Pelo Teorema 5.1, existem
m 2 N e �1; :::; �m 2 R+ com
Pm
i=1 �i = 1 tais que x =
Pm
i=1 �ixi, para alguma coleção de
pontos fx1; :::; xmg � A. Se m � n + 1, não há nada a ser demonstrado. Suponha, então,
que m > n + 1 e considere os m � 1 vetores (x1 � xm); :::; (xm�1 � xm). Como m > n + 1,
tais vetores são linearmente dependentes e, consequentemente, existem 
1; :::; 
m�1 2 R, não
todos eles iguais a zero, tais que

1(x1 � xm) + � � �+ 
m�1(xm�1 � xm) = 0:
De�na 
m := �
Pm�1
i=1 
i. Observe que

1x1 + � � � 
m�1xm�1 + 
mxm = 0
e
mX
i=1

i = 0.
Como �i > 0 pra todo i, nós podemos de�nir t� := supft 2 R++ : �i � t
i � 0 pra todo ig.
Note que
mX
i=1
(�i � t�
i)xi = x;
mX
i=1
(�i � t�
i) = 1
e �i � t�
i � 0 pra todo i, com igualdade para algum i. Ou seja, x pode ser escrito como
uma combinação convexa de menos que m elementos de A. Procedendo indutivamente, nós
obtemos o teorema. �
Em palavras, o teorema 5.2 nos diz que todo elemento do fecho convexo de algum A 2 Rn
pode ser expresso como uma combinação convexa de, no máximo, n+ 1 elementos de A.
Lema 5.6. Se A � Rn é compacto, então co(A) também é compacto.
Demonstração. Pegue (xm) tal quefxmg � co(A). Para cada m, pelo Teorema 5.2, existem
�m1 ; :::; �
m
n+1 � 0 com
Pn+1
i=1 �i = 1 e x
m
1 ; :::; x
m
n+1 2 A tais que
Pn+1
i=1 �
m
i x
m
i = x
m. Como
f�m1 g � [0; 1] e [0; 1] é compacto, existe �1 2 [0; 1] e uma subsequência (�
mk
1 ) de (�
m
1 ) tal que
�mk1 ! �1. Como fx
mk
1 g � A e A é compacto, existe x1 2 A e uma subsequência de (x
mk
1 ),
que vamos chamar novamente de (xmk1 ), tais que x
mk
1 ! x1. Procedendo desta forma para
i = 2; :::; n+1, nós obtemos subsequências (�mk1 ); :::; (�
mk
n+1) e (x
mk
1 ); :::; (x
mk
n+1) tais que, para
todo i, �mki ! �i 2 [0; 1] e x
mk
i ! xi 2 A. Além disto, como, para todo k,
Pn+1
i=1 �
mk
i = 1,
nós temos �1+ :::+�n+1 = 1. Mas então, xmk !
Pn+1
i=1 �ixi 2 co(A). Ou seja, co(A) satisfaz
compacticidade sequencial. �
Lema 5.7. Se I � Rn é aberto, então co(I) é aberto.
Demonstração. Pelo Corolário 5.1, int(co(I)) é um conjunto convexo. Note ainda que I �
int(co(I)). Isto implica que co(I) � int(co(I)) e, consequentemente, co(I) = int(co(I)), que
é um conjunto aberto. �
5.1. EXERCÍCIOS 29
5.1 Exercícios
Exercício 5.2. Dizemos que um subconjunto C de Rn é um cone se, pra todo x 2 C e
todo � � 0, nós temos �x 2 C. Se C é também convexo, nós dizemos que C é um cone
convexo. Seja agora C um subconjunto qualquer de Rn. Mostre que C é um cone convexo
se, e somente se, x1; x2 2 C and �1; �2 � 0 implica que �1x1 + �2x2 2 C.
Exercício 5.3. Mostre que se C1 e C2 são cones convexos em Rn, então C1 +C2 também é
um cone convexo.5.1 Além disto, mostre que C1 + C2 = co(C1 [ C2).
5.1Notação: Escrevemos C1 + C2 para representar o conjunto fx1 + x2 : x1 2 C1 e x2 2 C2g.
30 CAPÍTULO 5. CONJUNTOS CONVEXOS
Capítulo 6
Hiperplanos e Teoremas de Separação
De�nição 6.1. Um hiperplano H�a em Rn, em que � 2 R e a 2 Rn, é de�nido como o
conjunto dos pontos que satisfazem a equação ha; xi = �. Nós chamamos a de normal
do hiperplano. Isto vem do fato de que todo hiperplano é uma translação do hiperplano
ha; xi = 0.
De�nição 6.2. O semi-espaço positivo determinado pelo hiperplano H�a e denotado H
�+
a é
de�nido por
H�+a := fx 2 Rn : ha; xi > �g:
O semi-espaço negativo é de�nido por
H��a := fx 2 Rn : ha; xi < �g:
Já os semi-espaços fechados são de�nidos por
H
�+
a := fx 2 Rn : ha; xi � �g
e
H
��
a := fx 2 Rn : ha; xi � �g:
Teorema 6.1 (Separação de ponto e conjunto convexo fechado). Seja C � Rn um conjunto
convexo e fechado, e y 2 Rn n C. Então existe hiperplano H�a e " > 0 tais que, pra todo
x 2 C,
ha; yi > � + " > �� " > ha; xi:
Demonstração. De�na g : Rn ! R por g(x) := kxk. Pelo Exercício 3.2, nós sabemos que g
é contínua. De�na h : Rn ! Rn por h(x) = y � x. A função h também é contínua. Então
f := g � h também é contínua. Note que f(x) = ky � xk. Fixe z 2 C. De�na � := ky � zk.
Então, B(y; �) é um conjunto compacto. Como C é fechado, B(y; �) \ C também é um
conjunto compacto. Como f é contínua, existe x� 2 C tal que ky�x�k � ky�xk para todo
x 2 B(y; �)\C. É claro que isto implica que ky�x�k � ky�xk 8x 2 C. De�na a := y�x�
e note que
hy � x�; y � x�i = ky � x�k2 > 0:
31
32 CAPÍTULO 6. HIPERPLANOS E TEOREMAS DE SEPARAÇÃO
Isto implica que hy � x�; yi > hy � x�; x�i. De�na agora � := hy�x
�;yi+hy�x�;x�i
2
e " :=
(hy � x�; yi � �) =2. Note que
hy � x�; yi > � + " > �� " > hy � x�; x�i:
Agora �xe x 2 C e � 2 (0; 1). Note que, como x� minimiza a distância até y em C,
ky � x�k+ 2�hy � x�; x� � xi+ �2 kx� � xk2 = ky � �x� (1� �)x�k
� ky � x�k .
Isto implica que
2�hy � x�; x� � xi � ��2 kx� � xk2
()
hy � x�; x� � xi � ��
2
kx� � xk2 :
Como a expressão acima vale para todo � 2 (0; 1), nós temos que ter hy � x�; x� � xi � 0, o
que implica que hy � x�; xi � hy � x�; x�i < �� ". �
Nós agora precisamos do seguinte lema:
Lema 6.1. Se A � Rn é um conjunto convexo, então int(A) = int(cl(A)).
Intuição da Demonstração. Nós vimos no Exercício 5.1 que o lema é verdade sempre que
int(A) 6= ;. Para mostrar que o lema é verdade em geral nós precisamos usar um pouco
mais da estrutura linear de dimensão �nita do Rn. Como os detalhes da demonstração
são um pouco tediosos, aqui nós daremos apenas a intuição do argumento. É evidente que
int(A) � int(cl(A)). Considere agora um ponto x 2 int(cl(A)) (ver �gura 6.1). Isto implica
que existe uma bola aberta ao redor de x que está contida em int(cl(A)). Agora, pegue
pontos dentro desta bola aberta (os pontos x1, x2, x3 e x4 na �gura 6.1) que correspondam
aos vértices de um cubo ao redor de x. Para cada um desses pontos, pegue uma bola aberta
ao redor deles pequena o su�ciente. Como esses pontos pertencem a cl(A), dentro dessas
bolas abertas existem pontos que pertencem a A (os pontos y1, y2, y3 e y4 na �gura 6.1).
Como A é convexo, o fecho convexos desses pontos está contido em A (a região cinza na �gura
6.1). Agora é claro que x pertence ao interior deste novo conjunto e, consequentemente, x
pertence a int(A). �
Teorema 6.2 (Separação de ponto e conjunto convexo arbitrário). Seja C � Rn convexo
e y =2 C. Então, existe hiperplano H�a tal que ha; yi = � � ha; xi, 8x 2 C. Além disto, se
x 2 int(C), então � > ha; xi.
Demonstração. Se y =2 cl(C), o teorema é consequência do resultado anterior, pois C �
cl(C). Suponha, então, que y 2 cl(C). Como y =2 C � int(C), sabemos, do lema 6.1, que
y =2 int(cl(C)). Isto nos permite encontrar sequência (ym) tal que ym ! y e ym =2 cl(C),
8m. Do teorema anterior, sabemos que, para cada m, existe hiperplano H�am tal que:
ham; ymi > �m > ham; xi; 8x 2 cl(C):
33
Figura 6.1: Em Rn, ponto no interior do fecho pertence ao interior do conjunto.
Isto implica que, para cada m,
ham; ym � xi > 0; 8x 2 cl(C):
Sem perda de generalidade, podemos assumir que kamk = 1. Como famg � B(0; 1) e B(0; 1)
é compacto, (am) tem uma subsequência convergente amk ! a. Fixe x 2 cl(C). Como
amk ! a, ymk ! y e hamk ; ymk � xi é uma função contínua de amk e ymk ,
ha; y � xi = lim
mk!1
hamk ; ymk � xi � 0:
Como x foi escolhido arbitrariamente, isto mostra que ha; yi � ha; xi 8x 2 cl(C). Falta
mostrar que se x 2 int(C), então ha; xi < ha; yi. Para isto, suponha que ha; xi = ha; yi.
Como x 2 int(C), para � > 0 pequeno, x+ �a 2 int(C). Mas note que
ha; x+ �ai = ha; xi+ � kak2
= ha; xi+ �
> ha; yi.6.1
Isto contradiz o que demonstramos na primeira parte. Concluímos que ha; xi < ha; yi. �
Teorema 6.3 (Separação de conjuntos convexos). Sejam X;Y � Rn conjuntos convexos e
disjuntos. Então existe hiperplano H�a tal que ha; xi � � � ha; yi, para todo x 2 X e y 2 Y .
Demonstração. De�na C := X � Y = fx � y : x 2 X e y 2 Y g. Do Lema 5.2, sabemos
que C é convexo. Como X e Y são disjuntos, ~0 =2 C. Aplicando o teorema anterior, nós
encontramos um hiperplano H
a tal que ha; wi � 
 = ha;~0i = 0, 8w 2 C. Isto implica que
ha; xi � ha; yi para todo x 2 X e y 2 Y . Finalmente, de�na � := supfha; xi : x 2 Xg. É
claro que ha; xi � � � ha; yi, 8x 2 X e y 2 Y . �
6.1Como kamkk = 1 8k e amk ! a, kak = 1.
34 CAPÍTULO 6. HIPERPLANOS E TEOREMAS DE SEPARAÇÃO
Teorema 6.4 (Separação de conjuntos convexos com interior não vazio). Sejam X; Y � Rn
conjuntos convexos tais que int(X) 6= ? e int(X) \ Y = ?. Então existe hiperplano H�a tal
que ha; xi � � � ha; yi, para todo x 2 cl(X) e y 2 cl(Y ). Além disto, para todo x 2 int(X)
nós temos ha; xi < �.
Demonstração. Como int(X) é um conjunto aberto tal que int(X) \ Y = ?, nós sabemos
que int(X)\cl(Y ) = ?, pois Rnn(int(X)) é fechado e, portanto, cl(Y ) � Rnn(int(X)). Pelo
Corolário 5.1, int(X) é convexo. Pelo Lema 5.3, cl(Y ) também é convexo. Pelo Teorema
6.3, existe hiperplano H�a tal que ha; xi � � � ha; yi, 8x 2 int(X) e todo y 2 cl(Y ). Pegue
x 2 cl(X). Pelo Exercício 5.1, cl(X) = cl(int(X)) e, consequentemente, x 2 cl(int(X)).
Isto implica que existe (xm) tal que xm ! x e fxmg � int(X). Como ha; xmi � �, 8m, a
continuidade do produto interno agora implica que ha; xi � �. Finalmente, falta mostrar
que quando x 2 int(X), temos ha; xi < �. Nós fazemos isto usando exatamente o mesmo
argumento que utilizamos no Teorema 6.2. �
Teorema 6.5 (Separação deconjunto compacto e conjunto fechado). SejamK um subconjunto
compacto e convexo de Rn, e C um subconjunto convexo e fechado de Rn. Se K \ C = ?,
então existe hiperplano H�a e " > 0 tal que ha; xi < �� " < �+ " < ha; yi, para todo x 2 K
e y 2 C.
Demonstração. De�na A := K�C. Sabemos que A é convexo. Pegue sequência convergente
zm ! z tal que fzmg � A. Para cada m, existem xm 2 K e ym 2 C tais que zm = xm� ym.
Como K é compacto, existe subsequência (xmk) de (xm) tal que xmk ! x 2 K. Como
ymk = xmk � zmk , nós sabemos que ymk ! x� z. Como C é fechado, x� z 2 C. Isto implica
que z 2 A, portanto A é fechado. Como K \ C = ?, ~0 =2 A. Pelo teorema de separação de
ponto e conjunto fechado, existem hiperplano H
a e � > 0 tais que ha; wi < 
 � � < 
 + � <
ha;~0i = 0, para todo w 2 A. Isto implica que 
 < 0 e
ha; xi < ha; yi+ 
;
para todo x 2 K e y 2 C. De�na � := supfha; xi : x 2 Kg + j
j
2
e " := j
j
4
. Note que para
todo x 2 K,
ha; xi � �� j
j
2
< �� ":
Além disto, para todo y 2 C,
ha; yi � �� j
j
2
+ j
j = �+ j
j
2
> � + ":
Isto completa a demonstração do teorema. �
6.1 Exercícios
Exercício 6.1. Suponha que A � Rn seja convexo e esteja contido em algum semiespaço
fechado de Rn. Isto é, suponha que exista hiperplano H�a tal que A � �H�+a . Mostre que
cl(A) = \f �H�+a : A � �H�+a g. Isto é, cl(A) é a interseção de todos os semiespaços fechados
que contêm A.
6.1. EXERCÍCIOS 35
Exercício 6.2 (Teorema do Hiperplano Suporte). Seja A um conjunto convexo e suponha
que z seja um ponto de fronteira de A.6.2 Mostre que existe hiperplano H�a tal que ha; xi � �
pra todo x 2 A e ha; zi = �. Além disto, pra todo x 2 int(A) nós temos ha; xi < �.
Exercício 6.3. Seja f : Rn ! R uma função contínua, côncava (isto é, pra todo x e y em
Rn, e todo � 2 [0; 1], f(�x+ (1� �)y) � �f(x) + (1� �)f(y)), homogênea de grau 1 (isto é,
pra todo x 2 Rn e todo k > 0, f(kx) = kf(x)). Os passos a seguir demonstram um famoso
resultado em análise convexa.
(a) Argumente que f(0) = 0.
(b) De�na o epigrafo da função f por epi(f) := f(x; l) : x 2 Rn e l 2 R satisfaz l � f(x)g.
Use a continuidade de f para mostrar que epi(f) é um subconjunto fechado de Rn+1 e
use a concavidade de f para mostrar que epi(f) é um subconjunto convexo de Rn+1.
(c) Fixe x� 2 Rn. Argumente que (x�; f(x�)) é um ponto de fronteira do conjunto epi(f)
(isto é, (x�; f(x�)) 2 cl(epi(f)) n int(epi(f))).
Aplicando o Teorema do Hiperplano Suporte ao que aprendemos no item (c), nós
sabemos que existe a 2 Rn, 
 2 R, com (a; 
) 6= (�!0 ; 0), e � 2 R tal que h(a; 
); (x; l)i �
� = h(a; 
); (x�; f(x�))i, pra todo (x; l) 2 epi(f).
(d) Usando a homogeneidade de grau 1 da função f , argumente que � = 0.
(e) Argumente que necessariamente 
 > 0. Dica: Use a estrutura do conjunto epi(f) para
mostrar que 
 � 0. Depois disto argumente que não é possível que 
 = 0.
(f) Use o que você aprendeu nos ítens anteriores para mostrar que, pra todo x� 2 Rn,
f(x�) = minfha; x�i : a 2 Rn satisfaz ha; xi � f(x)8x 2 Rng.
6.2Isto é, z 2 cl(A) n int(A).
36 CAPÍTULO 6. HIPERPLANOS E TEOREMAS DE SEPARAÇÃO
Parte II
Otimização
37
Capítulo 7
Otimização Estática
Seja X � Rn e f : X ! R. Nós estamos interessados no seguinte problema:
max
x2X
f(x) (7.1)
O conjunto X é chamado de conjunto restrição e f é chamada de função objetivo.
O problema (7.1) signi�ca que queremos encontrar x� 2 X tal que f(x�) � f(x), 8x 2 X.
De�nição 7.1. Dizemos que x� 2 X é um máximo local se existe � > 0 tal que f(x�) � f(x)
para todo x 2 B(x�; �) \X. Se f(x�) > f(x) para todo x 2 (B(x�; �) \X) n fx�g, dizemos
que x� é um máximo local estrito. Podemos de�nir os conceitos de mínimo, mínimo local e
mínimo local estrito de maneira análoga.
7.1 Problemas sem Restrições
Dizemos que (7.1) é um problema sem restrição quando X é um conjunto aberto.
7.1.1 Otimização de funções diferenciáveis de uma variável
Suponha que X seja um intervalo aberto em R e que f seja derivável em x�. Se x� é um
máximo local, então existe � > 0 tal que f(x�) � f(x) para todo x 2 (x� � �; x� + �). Mas
então, para x� < x < x� + � nós temos:
f(x)� f(x�)
x� x� � 0
e para x� � � < x < x� nós temos
f(x)� f(x�)
x� x� � 0:
Como f é diferenciável em x�,
f 0(x�) = lim
x#x�
f(x)� f(x�)
x� x� � 0
39
40 CAPÍTULO 7. OTIMIZAÇÃO ESTÁTICA
e
f 0(x�) = lim
x"x�
f(x)� f(x�)
x� x� � 0:
Isto implica que f 0(x�) = 0.
Suponha agora que f seja de classe C(2) em uma vizinhança de x�. Isto é, f é duas vezes
continuamente diferenciável nesta vizinhança. Mais especi�camente, existe 
 > 0 tal que
f 00(x) está bem de�nida para todo x 2 (x� � 
; x� + 
) e f 00 é contínua em (x� � 
; x� + 
).
Do Teorema de Taylor, sabemos que 8x 2 (x� � �; x� + �) existe �x entre x e x� tal que
f(x) = f(x�) + f 0(x�)(x� x�) + 1
2
f 00(�x)(x� x�)2:
Quando x� é um máximo local, f 0(x�) = 0. Neste caso, a expressão acima pode ser escrita
como:
f 00(�x) =
2(f(x)� f(x�))
(x� x�)2 � 0:
Quando x ! x�, como x � �x � x� ou x� � �x � x, temos que �x ! x�. Como f 00 é
contínua em (x� � �; x� + �), isto implica que f 00(x�) � 0.
Esta análise pode ser resumida no seguinte teorema:
Teorema 7.1. Seja X um intervalo aberto em R. Seja f : X ! R e x� 2 X um máximo
local de f em X. Se f é diferenciável em x�, então f 0(x�) = 0. Se f é de classe C(2) em
uma vizinhança de x�, então f 00(x�) � 0.
Nós também podemos demonstrar o seguinte resultado:
Teorema 7.2. Seja X um intervalo em R e seja f uma função de classe C(2) em um intervalo
ao redor de x� 2 X. Se f 0(x�) = 0 e f 00(x�) < 0, então x� é um máximo local estrito de f
em X.
Demonstração. Como f 00(x�) < 0 e f 00 é contínua em uma vizinhança de x�, sabemos que
existe � > 0 tal que f 00(x) < 0 para todo x 2 (x� � �; x� + �) e f é de classe C(2) em
(x� � �; x� + �). Usando o Teorema de Taylor (como no teorema anterior), nós sabemos
que para todo x 2 (x� � �; x� + �) n fx�g existe �x entre x e x� tal que f(x) � f(x�) =
1
2
f 00(�x)(x� x�)2 < 0. Isto é, f(x�) > f(x) para todo x 2 (x� � �; x� + �) n fx�g. �
7.1.2 Otimização de funções diferenciáveis de múltiplas variáveis
Seja f : Rn ! R e �xe x� 2 Rn. Para i = 1; :::; n, de�na gi : R ! R por gi(t) :=
f(x�1; :::; x
�
i�1; t; x
�
i+1; :::; x
�
n). A derivada parcial de f em relação à i-ésima coordenada no
ponto x�, @f
@xi
(x�), é simplesmente
@f
@xi
(x�) := g0i(x
�
i ):
7.1. PROBLEMAS SEM RESTRIÇÕES 41
De�nição 7.2. O vetor com todas as derivadas parciais de f no ponto x� é chamado de
gradiente de f em x� e é denotado por:
rf(x�) :=
�
@f
@x1
(x�); : : : ;
@f
@xn
(x�)
�
:
De�nição 7.3. A matriz2664
@2f(x�)
@x12
� � � @
2f(x�)
@x1@xn
...
. . .
...
@2f(x�)
@xn@x1
� � � @
2f(x�)
@x2n
3775
n�n
=
�
@2f(x�)
@xi@xj
�
ij
é chamada de matriz hessiana de f em x� e denotada Hf (x�).
Considere agora f : Rn ! R e suponha que f é de classe C(2) em uma bola aberta
B(x�; �) ao redor de x� 2 Rn. O Teorema de Taylor nos diz que para todo x 2 B(x�; �),
existe �x = �x + (1 � �)x� para algum � 2 [0; 1] tal que f(x) = f(x�) + rf(x�)(x � x�) +
1
2
(x� x�)THf (�x)(x� x�).7.1
De�nição 7.4. Dizemos que uma matriz A, n � n, é negativa semide�nida se para todo
x 2 Rn, xTAx � 0. Se xTAx < 0 sempre que x 6= ~0, então dizemos que A é negativa de�nida.
Teorema 7.3. Seja X um subconjunto aberto do Rn. Seja f : X ! R e suponha que x� é
um máximo local de f em X. Se f tem derivadas parciais em x�, então
rf(x�) = ~0: (7.2)
Se f é de classe C(2) em uma bola aberta B(x�; �), então H(x�) é negativa semide�nida.
Demonstração. Fixe uma coordenada i e de�na gi : R! R por:
gi(xi) := f(x
�
1; :::; x
�
i�1; xi; x
�
i+1; :::; x
�
n)
Como X é aberto, existe � > 0 tal que (x�1; :::; x
�
i�1; x
�
i + "; x
�
i+1; :::; x
�
n) 2 X se " 2 (��; �).
Além disto, claramente x�i é um máximo local de gi em (x
�
i��; x�i+�). Usando o Teorema 7.1,
sabemos que g0i(x
i
�) = 0. Mas
@f(x�)
@xi
= g0i(x
i
�). Como isto vale para todo i, nós aprendemos
que rf(x�) = ~0. Como f é de classe C(2) em uma bola aberta B(x�; �) ao redor de x�, o
Teorema de Taylor nos garante que, para qualquer x 2B(x�; �), existe � 2 [0; 1] tal que �x
de�nido por �x := �x� + (1� �)x satisfaz:
f(x) = f(x�) +rf(x�)(x� x�) + 1
2
(x� x�)TH(�x)(x� x�)
Como rf(x�) = 0, a expressão acima pode ser escrita como:
(x� x�)TH(�x)(x� x�) = 2(f(x)� f(x�))
7.1Note que rf foi de�nido como um vetor linha, portanto as multiplicações estão bem de�nidas.
42 CAPÍTULO 7. OTIMIZAÇÃO ESTÁTICA
Como x� é uma máximo local, existe 0 < " < � tal que f(x�) � f(x) para todo x 2 B(x�; ").
Agora, �xe z 2 Rn. Para cada m 2 N, pegue xm 2 B(x�; ") tal que d(x�; xm) < 1
m
e
xm�x� = km � z, para algum km > 0. Pelo que vimos antes, existe �xm entre xm e x� tal que:
(xm � x�)TH(�xm)(xm � x�) = 2(f(xm)� f(x�)) � 0
Isto implica que (km)2zTH(�xm)z � 0, o que só pode ocorrer se zTH(�xm)z � 0. Como
�xm ! x�, isto implica que zTH(x�)z � 0. Como z foi escolhido arbitrariamente, isto mostra
que H(x�) é negativa semide�nida. �
Teorema 7.4. Seja X um conjunto aberto em Rn. Seja f : X ! R uma função de classe
C(2) em uma bola B(x�; �) ao redor de x� 2 X. Suponha ainda que rf(x�) = 0. Se H(x�) é
negativa de�nida, então x� é um máximo local estrito de f . Se X é convexo, f é de classe
C(2) em X e H(x) é negativa semide�nida em todo x 2 X, então x� é um máximo global.
Se H(x) for negativa de�nida em todo x 2 X, então x� é um máximo global estrito.
Demonstração. ComoH(x�) é negativa de�nida e f é de classe C(2) em B(x�; �), existe 
 < �
tal que H(x) é negativa de�nida em todo x 2 B(x�; 
). Como f é de classe C(2) em B(x�; 
),
para todo x 2 B(x�; 
) existe � 2 [0; 1] tal que �x := �x+ (1� �)x� satisfaz:
f(x) = f(x�) +rf(x�)(x� x�) + 1
2
(x� x�)TH(�x)(x� x�):
Como, por hipótese, rf(x�) = ~0, a expressão acima pode ser escrita como
f(x)� f(x�) = 1
2
(x� x�)TH(�x)(x� x�):
Como H(�x) é negativa de�nida, sempre que x 6= x� o lado direito é negativo, o que implica
que f(x) < f(x�) 8x 2 B(x�; 
). Ou seja, x� é um ponto de máximo local estrito. Para
provar a segunda parte, note que podemos repetir os passos acima, para x 2 X, e assim
concluirmos que x� é um máximo global. A terceira parte é inteiramente análoga. �
Exemplo 7.1. Encontre os máximos e mínimos locais da seguinte função:
f(x1; x2) = x1
2 � 4x1 + 2x22 + 7:
Vamos primeiro encontrar os pontos em que @f
@x1
(x) = @f
@x2
(x) = 0:
� @f
@x1
(x) = 0 () x1 = 2
� @f
@x2
(x) = 0 () x2 = 0
Vamos agora calcular H(2; 0):
@2f(x)
@x12
= 2 ;
@2f(x)
@x1x2
=
@2f(x)
@x2x1
= 0 ;
@2f(x)
@x22
= 4
Logo:
H(2; 0) =
�
2 0
0 4
�
7.1. PROBLEMAS SEM RESTRIÇÕES 43
Fixe um vetor (z1; z2) 2 R2. Note que:�
z1 z2
� � 2 0
0 4
��
z1
z2
�
= 2z21 + 4z
2
2
Ou seja, H(x) é positiva de�nida para todo x 2 R2. Aplicando o Teorema 7.4 a (�f), nós
concluímos que (2; 0) é um mínimo global.
7.1.3 Maximização de funções côncavas
Teorema 7.5. Seja f uma função côncava de�nida num subconjunto convexo C de R2.
(i) Se x� é um máximo local de f em C, então x� é um máximo global em C.
(ii) O conjunto de pontos de máximo de f em C é convexo.
(iii) Se f é estritamente côncava e x� é um ponto de máximo, então x� é único.
(iv) Se f não é constante e x� é um ponto de mínimo, então x� é um ponto de fronteira de
C.
Demonstração.
(i) Suponha que x� não seja um máximo global. Isto é, suponha que exista x 2 C com
f(x) > f(x�). Como f é côncava, isto implica que, para todo � 2 (0; 1),
f(�x+ (1� �)x�) � �f(x) + (1� �)f(x�) > f(x�):
Isso mostra que x� não é máximo local.
(ii) Suponha que x e y sejam máximos de f em C. Para qualquer � 2 (0; 1), nós temos
f(�x+ (1� �)y) � �f(x) + (1� �)f(y) = f(x):
Como x é ponto de máximo, isto implica que f(�x + (1 � �)y) = f(x). Ou seja,
�x+ (1� �)y maximiza f .
(iii) Suponha que x e y sejam pontos de máximo. Como f é estritamente côncava, para
qualquer � 2 (0; 1), f(�x + (1 � �)y) � �f(x) + (1 � �)f(y), com igualdade somente
se x = y. Como x é ponto de máximo, isto implica que x = y.
(iv) Suponha que x seja um ponto de mínimo de f , mas x 2 int(C). Como f não é
constante, existe y 2 C tal que f(y) > f(x). De�na z := �x + (1 � �)y para � > 1
próximo o su�ciente de 1, para que z 2 C. Tal z existe, já que x 2 int(C). Note que
x = 1
�
z + (1� 1
�
)y. Como f é côncava e x é ponto de mínimo, temos que
f(x) = f
�
1
�
z +
�
1� 1
�
�
y
�
� 1
�
f(z) +
�
1� 1
�
�
f(y) > f(x);
o que é uma contradição. Concluímos que x é um ponto de fronteira de C. �
Teorema 7.6. Seja f côncava e diferenciável em um conjunto aberto e convexo C. Então
f atinge um máximo em x� se, e somente se, rf(x�) = ~0.
Em palavras, para funções côncavas a condição de primeira ordem é necessária e su�ciente.
44 CAPÍTULO 7. OTIMIZAÇÃO ESTÁTICA
7.2 Problemas com Restrições
Seja X um subconjunto aberto e convexo de Rn. Sejam f; g1; :::; gm; h1; :::; hk funções reais
de classe C(1) em X. Estamos interessados no seguinte problema:
max
x2X
f(x)
s:a: g1(x) � 0
...
gm(x) � 0
h1(x) = 0
...
hk(x) = 0
(*)
Teorema 7.7 (Condições de Fritz-John). Se x� é uma solução de (*), então existem �0; :::; �m �
0 e �1; :::; �k 2 R tais que:
(i) (�0; :::; �m; �1; :::; �k) 6= ~0.
(ii) �igi(x�) = 0 para i = 1; :::;m.
(iii) �0
@f(x�)
@xi
+ �1
@g1(x�)
@xi
+ � � �+ �m@gm(x
�)
@xi
+ �1
@h1(x�)
@xi
+ � � �+ �k
@hk(x
�)
@xi
= 0 para i = 1; :::; n.
Dado um problema de maximização como em (*), um ponto x� que satisfaz as condições
no Teorema 7.7 é chamado de ponto crítico. As condições (i), (ii) e (iii) são chamadas de
condições de primeira ordem (CPO) do problema. Em palavras, o Teorema 7.7 diz que todo
ponto de máximo é um ponto crítico.
O Teorema 7.7 nos sugere o seguinte método para encontrarmos os pontos de máximo de
um problema como em (*):
Primeiramente, identi�que todos os pontos críticos do problema. Tipicamente, este será
um conjunto �nito. Agora maximize a função f apenas entre os pontos críticos. Os pontos
que maximizam a f entre os pontos críticos são também as soluções de (*).
Observação 7.1. O Teorema 7.7 não garante que o problema tenha solução. Ele apenas nos
fornece algumas características das soluções quando estas existem. Em geral, nós primeiro
precisaremos de algum tipo de argumento para garantir que o problema tenha solução, para
somente então aplicar o método sugerido acima para encontrar as soluções do problema.
Exemplo 7.2.
min
(x1;x2)2R2
(x1 � 1)2 + x22
s:a: 2kx1 � x22 � 0
Vamos resolver com k = 1 e k = 2
3
. Para k = 1:
max
(x1;x2)2R2
�(x1 � 1)2 � x22
s:a: x2
2 � 2kx1 � 0
7.2. PROBLEMAS COM RESTRIÇÕES 45
Para aplicar o Teorema 7.7, nós escrevemos o lagrangeano do problema. Ou seja, de�nimos
uma função L(�0; �1; x1; x2) por:
L(�0; �1; x1; x2) = �0[�(x1 � 1)2 � x22] + �1(x22 � 2x1)
A condição (iii) do Teorema torna-se:
x1 : �2�0(x1 � 1)� 2�1 = 0
x2 : �2�0x2 + 2�1x2 = 0
Note que a primeira condição acima implica que �1 = 0 se �0 = 0, o que contradiz (i). Nós
concluímos que para qualquer ponto crítico do problema, �0 > 0. Sem perda de generalidade,
podemos assumir que �0 = 1. As condições acima viram:
x1 : �2(x1 � 1)� 2�1 = 0
x2 : �2x2 + 2�1x2 = 0
Vamos dividir em dois casos:
Caso 1: x22 � 2x1 > 0:
Neste caso, a condição (ii) no Teorema 7.7 implica que �1 = 0. Isto agora implica que
x1 = 1 e x2 = 0. Mas note que (1; 0) não satisfaz a restrição e, portanto, não existe ponto
crítico neste caso.
Caso 2: x22 = 2x1:
Da CPO em relação a x1, nós temos que �1 = 1� x1. Substituindo na CPO em relação
a x2, nós obtemos que
x2 = (1� x1)x2:
Se x2 6= 0, então a condição acima implica que x1 = 0, o que contradiz x22 = 2x1. Nós
concluímos que x1 = x2 = 0.
Vamos agora argumentar que o problema tem solução. Para isto, note que a solução do
problema
max
(x1;x2)2R
�(x1 � 1)2 � x22
s:a: x2
2 � 2x1 � 0
�1 � x2 � 1
0 � x1 � 2
coincide com a solução do problema original. Note que as restrições do novo problema formam
um conjunto compacto. Como a função objetivo é contínua, o Teorema de Weierstrass
garante que o problema tem solução. Como só temos um ponto crítico, necessariamente esse
ponto é a solução do problema.
Considere agora o problema com k = 2
3
. Isto é,
max
(x1;x2)2R2
�(x1 � 1)2 � x22s:a: x2
2 � 4
3
x1 � 0
O lagrangeano do problema é:
L(�0; �1; x1; x2) = �0[�(x1 � 1)2 � x22] + �1(x22 �
4
3
x1):
46 CAPÍTULO 7. OTIMIZAÇÃO ESTÁTICA
As CPO em relação a x1 e x2 são:
x1 : �2�0(x1 � 1)�
4
3
�1 = 0
x2 : �2�0x2 + 2�1x2 = 0
O mesmo argumento de antes garante que �0 > 0 e, portanto, podemos assumir que �0 = 1.
As CPO tornam-se:
x1 : �2(x1 � 1)�
4
3
�1 = 0
x2 : �2x2 + 2�1x2 = 0
Caso 1: x22 � 43x1 > 0:
Neste caso, a condição (ii) no Teorema 7.7 implica que �1 = 0, o que implica que x1 = 1
e x2 = 0. Mas note que (1; 0) não satisfaz a restrição e, portanto, não temos ponto crítico
neste caso.
Caso 2: x22 � 43x1 = 0:
Isolando �1 na CPO em relação a x1 e substituindo na restrição em relação a x2, temos
�2x2 = 3(x1 � 1)x2. Multiplicando por x2 dos dois lados:
�2x22 = 3(x1 � 1)x22:
Isolando x22 na restrição do caso e substituindo na equação acima:
�8
3
x1 = 4(x1 � 1)x1;
o que implica que x1 = 0, ou x1 � 1 = �23 . Isto é, ou x1 = 0, ou x1 =
1
3
. Isto implica que as
soluções do sistema são (0; 0),
�
1
3
; 2
3
�
e
�
1
3
;�2
3
�
. Encontramos, então, 3 pontos críticos.
Argumento similar ao que usamos antes garante que o problema tem solução. A solução
será o vetor que maximizar a função objetivo dentre os pontos críticos. Observe que
f(0; 0) = �(0� 1)2 � 02 = �1
f
�
1
3
;
2
3
�
= �
�
2
3
�2
�
�
2
3
�2
= �8
9
f
�
1
3
;�2
3
�
= �
�
2
3
�2
�
�
�2
3
�2
= �8
9
:
Logo, as soluções do problema são
�
1
3
; 2
3
�
e
�
1
3
;�2
3
�
.
Exemplo 7.3.
max
(x1;x2)2R
�x12 � (x2 + 1)2
s:a: 4� x12 � x22 � 0
x1 � 1� x2 2 � 0
x1 + 2x2 � 1 � 0
Note primeiro que o conjunto formado pela interseção de todas as restrições é compacto (ver
�gura 7.1). Como a função objetivo é contínua, isto implica que o problema tem solução. O
7.2. PROBLEMAS COM RESTRIÇÕES 47
Figura 7.1: Conjunto restrição do Exemplo 7.3
lagrangeano do problema é:
L = �0[�x12 � (x2 + 1)2] + �1(4� x12 � x22) + �2(x1 � 1� x22) + �3(x1 + 2x2 � 1):
As condições de primeira ordem são:
x1 : �2�0x1 � 2�1x1 + �2 + �3 = 0
x2 : �2�0(x2 + 1)� 2�1x2 � 2�2x2 + 2�3 = 0
Se a primeira e a segunda restrições forem ativas, então:
x2
2 = x1 � 1
x2
2 = 4� x12
�
() x1 =
�1 +
p
21
2
e x2 = �
s
�3 +
p
21
2
:
No entanto, se
x2 = �
s
�3 +
p
21
2
;
a terceira restrição não é satisfeita. Por outro lado, se
x2 =
s
�3 +
p
21
2
;
então x1 + 2x2 � 1 > 0. Ou seja, a terceira restrição não é ativa. Podemos, portanto,
descartar o caso de as três restrições serem simultaneamente ativas. Vamos analisar os casos
restantes:
Caso 1: Nenhuma restrição é ativa.
Neste caso, �1 = �2 = �3 = 0 e �0 > 0. Podemos tomar �0 = 1. Das CPO temos que
x1 = 0 e x2 = �1. Mas o ponto (0;�1) não satisfaz a segunda restrição, portanto não pode
ser ponto crítico.
48 CAPÍTULO 7. OTIMIZAÇÃO ESTÁTICA
Caso 2: Apenas a primeira e a segunda restrições são ativas.
Já encontramos que, neste caso,
x1 =
�1 +
p
21
2
e x2 =
s
�3 +
p
21
2
Além disto, sabemos que este ponto satisfaz todas as restrições.
Caso 3: Apenas a primeira e a terceira restrições são ativas.
Neste caso, �2 = 0. As condições de primeira ordem viram:
x1 : �2�0x1 � 2�1x1 + �3 = 0
x2 : ��0(x2 + 1)� �1x2 + �3 = 0
Observe ainda que a segunda restrição implica que x1 > 1. Da terceira restrição em
igualdade, nós obtemos que x1 = 1 � 2x2. Dada a nossa observação anterior, isto só pode
acontecer se x2 < 0. Note agora que se �0 = 0, então as condições de primeira ordem
implicam que �3 = 2�1x1 e �3 = �1x2. Como x1 > 0 e x2 < 0, isto só pode ocorrer se
�1 = �3 = 0, o que não pode acontecer. Nós concluímos que �0 > 0 e, sem perda de
generalidade, nós podemos assumir que �0 = 1. As condições de primeira ordem viram:
x1 : �2x1 � 2�1x1 + �3 = 0
x2 : �(x2 + 1)� �1x2 + �3 = 0
Isolando �3 na condição em relação a x1, substituindo na em relação a x2 e rearranjando,
nós obtemos
x2 =
2x1 � 1 + 2�1x1
1 + �1
:
Como x1 > 1, tal condição implica que x2 > 0, o que já vimos que viola a terceira restrição.
Nós concluímos que não existe ponto crítico neste caso.
Caso 4: A segunda e a terceira restrições são ativas.
Resolvendo o sistema formado pela segunda e terceira restrições em igualdade, obtemos
x2(2 + x2) = 0. Então x2 = 0 ou x2 = �2. Se x2 = �2, x1 = 5, mas o ponto (5;�2)
não satisfaz a primeira restrição e, portanto, não é ponto crítico. Caso x2 = 0, temos que
x1 = 1. Este ponto satisfaz todas as restrições e, mesmo sem checar que ele satisfaz todas
as condições para um ponto crítico, vamos guardá-lo.
Caso 5: Apenas a primeira restrição é ativa.
Neste caso �2 = �3 = 0. As condições de primeira ordem viram:
x1 : �2�0x1 � 2�1x1 = 0
x2 : �2�0(x2 + 1)� 2�1x2 = 0
Como, da segunda restrição nós sabemos que x1 > 1, se �0 = 0, então a condição de primeira
ordem em relação a x1 implica que x1 = 0, o que não pode ser verdade. Nós aprendemos que
�0 > 0 e, sem perda de generalidade, podemos assumir que �0 = 1. Agora, como �1 � 0, a
condição de primeira ordem em relação a x1 implica que x1 = 0. Como a segunda restrição
implica que x1 > 1, nós vemos que não existem pontos críticos neste caso.
7.2. PROBLEMAS COM RESTRIÇÕES 49
Caso 6: Apenas a segunda restrição é ativa.
Neste caso �1 = �3 = 0. Da condição de primeira ordem em relação a x1, nós vemos que
se �0 = 0, então nós também temos �2 = 0, o que não pode ocorrer. Nós concluímos que
�0 > 0 e, sem perda de generalidade, nós podemos assumir que �0 = 1. As condições de
primeira ordem viram:
x1 : �2x1 + �2 = 0
x2 : �(x2 + 1)� �2x2 = 0
Da condição de primeira ordem em relação a x1, nós obtemos que �2 = 2x1. Como a
primeira restrição implica que x1 < 2 e a segunda restrição implica que x1 � 1, isto implica
que 2 � �2 < 4. Isolando x2 na condição de primeira ordem em relação a x2 nós obtemos
que
x2 = �
1
1 + �2
:
Como 2 � �2 < 4, isto implica que �13 � x2 < �
1
5
. Agora, a segunda restrição em igualdade
implica que
x1 = 1 + x2
2 � 10
9
:
Mas então,
x1 + 2x2 � 1 <
10
9
� 2
5
� 1
= �13
45
< 0:
Ou seja, a terceira restrição não é satisfeita. Concluímos que não existem pontos críticos
neste caso.
Caso 7: Apenas a terceira restrição é ativa.
Agora �1 = �2 = 0. Da primeira CPO, nós vemos que se �0 = 0, então �3 = 0, o que
não pode ocorrer. Nós aprendemos que �0 > 0 e, sem perda de generalidade, nós podemos
assumir �0 = 1. As condições de primeira ordem viram:
x1 : �2x1 + �3 = 0
x2 : �(x2 + 1) + �3 = 0
Agora, da primeira e segunda CPO�s nós temos que �3 = 2x1 e �3 = x2 + 1. Isto implica
que x2 = 2x1 � 1. Substituindo isto na terceira restrição em igualdade, nós obtemos que
x1 =
3
5
. Como nós sabemos que a segunda restrição implica que x1 � 1, nós concluímos que
não existem pontos críticos neste caso.
Nós temos, então, 2 candidatos a máximo. Os pontos
�
�1+
p
21
2
;
q
�3+
p
21
2
�
e (1; 0). É
fácil ver que entre estes pontos quem maximiza a função objetivo é (x1; x2) = (1; 0):
50 CAPÍTULO 7. OTIMIZAÇÃO ESTÁTICA
Exemplo 7.4. Considere o seguinte problema de otimizaçãoo:
min
(x;y)2R2
x2 + y2
s:a: x2 + y2 � 4
y2 � x
�2y � x� 1
�2y � x� 2
Vamos primeiro argumentar que o problema tem solução. Para ver isto, note que o conjunto
restrição do problema é
X = f(x; y) 2 R2 : x2 + y2 � 4g \ f(x; y) 2 R2 : y2 � xg
\f(x; y) 2 R2 : �2y � x� 1g \ f(x; y) 2 R2 : �2y � x� 2g
Todos os conjuntos acima são fechados e o primeiro deles é compacto (por ser uma bola
fechada). Isto implica que X é compacto. Como x2 + y2 é uma função contínua, o Teorema
deWeierstrass nos garante que, seX 6= ?, então o problema tem solução. Como (�1; 1) 2 X,
nós concluímos que o problema tem solução.
Vamos agora encontrar a solução do problema. Note que a primeira restrição é irrelevante,
já que o problema minimiza exatamente x2 + y2, que é o que aparece do lado esquerdo da
restrição. Podemos, portanto, ignorar a primeira restrição. Note ainda que a terceira e a
quarta restrições não podem ser ativas ao mesmo tempo. O problema pode ser reescrito
como:
max
(x;y)2R2
�x2 � y2
s:a: y2 � x � 0
x+ 2y � 1 � 0
2� x� 2y � 0
O lagrangeano do problema é
L = �0(�x2