Upload
mrmprotegido
View
56
Download
2
Embed Size (px)
DESCRIPTION
Curso de Análise convexa para economistas.
Citation preview
Analise Convexa
1. Conjuntos convexos
1.1. Casca convexa, ponto extremo, cone
2. Hiperplanos: suporte, separador, teorema da separacao
3. Funcoes convexas
4. Teoremas de funcoes convexas
5. Conjunto poliedral e politopo
6. Exerccios
cReinaldo M. Palharespag.1 Fund. Controle Robusto via Otimizacao Bloco 2
Analise Convexa
Definicao Um conjunto C e dito ser afim se a reta que passa por dois pontos distintos
quaisquer em C esta em C
Definicao Dados dois pontos quaisquer p1, p2 C, e um escalar real , denomina-se
p1 + (1 )p2 C
uma combinacao afim de p1 e p2
Nota C e um conjunto afim se contem a combinacao afim de quaisquer dois pontos
em C
cReinaldo M. Palharespag.2 Fund. Controle Robusto via Otimizacao Bloco 2
Analise Convexa
Generalizacao Se C e um conjunto afim, p1, p2, . . . , pj C, e
jXk=1
k = 1, entao
1p1 + 2p2 + + jpj C
Lema Se C e um conjunto afim e p0 C , entao o conjunto
G = C p0 =
p p0
p C
ffe um subespaco
Dem. Se G e um subespaco entao, G 6= e fechado sob as operacoes de soma e
multiplicacao por escalar. Suponha que g1, g2 G e , R, entao g1 + p0 C e
g2 + p0 C de modo que
g1 + g2 + p0 = (g1 + p0) + (g2 + p0) + (1 ) p0 C
como C e afim, e + + (1 ) = 1, conclui-se que g1 + g2 G pois
g1 + g2 + p0 C
cReinaldo M. Palharespag.3 Fund. Controle Robusto via Otimizacao Bloco 2
Analise Convexa
Nota O conjunto afim C pode ser escrito como um subespaco mais uma constante da
forma
C = G + p0 =
g + p0
g G
ff
Definicao A dimensao de um conjunto afim C e a dimensao do subespaco
G = C p0, sendo p0 um elemento qualquer de C
Exemplo C =x Rn | Ax = y, A Rmn , y Rm
e um conjunto afim?
Considere x1, x2 C, entao para qualquer ,
A (x1 + (1 )x2) = A(x1) + (1 )Ax2
= y + (1 )y
= y
o que mostra que a combinacao afim x1 + (1 )x2 C.
cReinaldo M. Palharespag.4 Fund. Controle Robusto via Otimizacao Bloco 2
Conjunto Convexo
Definicao Um conjunto C e convexo se para qualquer par de pontos p1 e p2 em C, e
um escalar [0, 1], a combinacao convexa dada por p1 + (1 )p2 C
Nota Todo conjunto afim e convexo...
Generalizacao Qualquer ponto da forma
1p1 + 2p2 + + jpj , sendo que
jXk=1
= 1 e j 0
e uma combinacao convexa dos pontos p1, , pj
Nota Convexidade pode ser definida para qualquer subconjunto de um espaco vetorial
real ou complexo, inclusive o conjunto vazio
Exemplo Uma reta e afim
Exemplo Um segmento de reta (fechado) e convexo, mas nao afim (a nao ser que se
reduz a um ponto)...
cReinaldo M. Palharespag.5 Fund. Controle Robusto via Otimizacao Bloco 2
Conjuntos Convexos
Exemplo Um conjunto elipsoidal da forma
C =
p
(p pc)T P1 (p pc) 1, p Rn , P = P T 0
ff
e convexo. pc e o centro do elipsoide ep(P ) fornecem o tamanho dos semi eixos
Teorema
1. Se C e D sao conjuntos convexos entao C +D e convexo
2. Se C e um conjunto convexo entao
C , {p2 | p2 = p1; R; p1 C} e convexo
3. A interseccao de uma colecao de conjuntos convexos e convexo
Dem. 3) Se p1, p2 TnCn entao p1, p2 Cn , n. Como Cn e convexo, entao
para qualquer [0, 1], p1 + (1 )p2 Cn , n. Portanto, [0, 1],
p1 + (1 )p2 TnCn
cReinaldo M. Palharespag.6 Fund. Controle Robusto via Otimizacao Bloco 2
Casca Convexa
Definicao Dado um conjunto C qualquer, o menor conjunto convexo que contem C e
denominado casca convexa (e denotado por co{C})
C
Em outras palavras, a casca convexa de C e interseccao de todos os conjuntos convexos
contendo C. Ou a combinacao convexa de todos os pontos em C
Definicao C 6= , C X , co{C} (sendo X um espaco vetorial)
cReinaldo M. Palharespag.7 Fund. Controle Robusto via Otimizacao Bloco 2
Vertices
Fato A combinacao convexa pode ser generalizada para n pontos em C
p =nXi=1
ipi, i 0 enXi=1
i = 1
p1
p2
p3
p4
Definicao Todo ponto p C X tal que @p1, p2 C, p1 6= p2, que satisfaca
p = p1 + (1 )p2, (0, 1) e denominado ponto extremo ou vertice
Teorema Qualquer conjunto convexo e compacto e a casca convexa de seus vertices
cReinaldo M. Palharespag.8 Fund. Controle Robusto via Otimizacao Bloco 2
Cones
Definicao Um conjunto C e um cone se p C e 0 implica p C
Definicao Um cone convexo e um cone + conjunto convexo, ie para qualquer
p1, p2 C e 1, 2 0, 1p1 + 2p2 C
Nota O cone acima tem vertice em 0 e arestas cruzando os pontos p1 e p2
Exemplos
1. Cone:
2. Cone convexo?
cReinaldo M. Palharespag.9 Fund. Controle Robusto via Otimizacao Bloco 2
Cones
3. Conjunto das matrizes simetricas semidefinidas positivas
Sn = {A Rnn | A = AT , A 0}
e um cone convexo: se 1, 2 0 e B,C Sn , entao 1B + 2C S
n
Veja que isto e um consequencia direta da caracterizacao de uma forma quadratica
semidefinida positiva. Por exemplo, para qualquer x Rn , entao
xT (1B + 2C)x = xT1Bx + x
T2Cx 0
se B 0, C 0, 1, 2 0
cReinaldo M. Palharespag.10 Fund. Controle Robusto via Otimizacao Bloco 2
Hiperplanos ou Funcoes Afins
Definicao Denomina-se um hiperplano em X um conjunto
H =nx X | pT x = b, 0 6= p X , b R
oe p H . Naturalmente a funcao afim pT x b e nula em X
Para X = R2 e b = 1, se pT =h1 1
ie H e o conjunto dos x R2 tal que gera-se
a reta na figura abaixo
p, x = 1p
x
x
x
1
1
cReinaldo M. Palharespag.11 Fund. Controle Robusto via Otimizacao Bloco 2
Hiperplanos
Um hiperplano e um subespaco linear onde dim(H) =dim(X ) 1. Exemplo: a
reta e um subespaco linear do R2...
Para x1, x2 H e 0 x3 = x1 + (1 )x2 H ?
pT x3 = pT x1 + (1 )p
T x2 = b + (1 )b = b
Um hiperplano divide o espaco em dois semi-espacos fechados:
H =nx X | pT x b
oe H =
nx X | pT x b
oH e o semi-espaco na direcao de p e H na direcao de p. Estes semi-espacos sao
convexos, porem nao-afins
cReinaldo M. Palharespag.12 Fund. Controle Robusto via Otimizacao Bloco 2
Hiperplanos Suporte
Definicao Um hiperplano H e denominado hiperplano suporte de um conjunto
convexo C, se C H (ou C H) e H tem pontos em comum com B{C}
Em outras palavras, H e um hiperplano suporte de C se
1. inf{pT x | x C} = b (entao C H)
2. ou sup{pT x | x C} = b (entao C H)
x
C H
x B{C}
cReinaldo M. Palharespag.13 Fund. Controle Robusto via Otimizacao Bloco 2
Hiperplanos Suporte
Teorema Considere um conjunto convexo C X . Se x 6 int{C} e int{C} 6=
H : x H e C H ou C H
C
x
xi
p
H
1. pT (xi x) 0, xi C C H
2. pT (xi x) 0, xi C C H
cReinaldo M. Palharespag.14 Fund. Controle Robusto via Otimizacao Bloco 2
Cone Dual
Definicao Considere um cone C. O conjunto
C , {y | xT y 0, x C}
e chamado cone dual de C
Interpretacao y C sse y e normal a um hiperplano que suporta C na origem
Cy
Note que o semi-espaco com o y normal e interno contem o cone C, entao y C
cReinaldo M. Palharespag.15 Fund. Controle Robusto via Otimizacao Bloco 2
Hiperplanos Separadores
Definicao Um hiperplano H e denominado hiperplano separador se para dois
conjuntos convexos C1 e C2 H : C1 H e C2 H
Os conjuntos sao estritamente separaveis se C1 H< e/ou C2 H>
C1C1C1
C2C2
C2H
H
H
+ Exemplo Se C1 = C2 = {0} R, entao o hiperplano x = 0 separa C1 e C2
cReinaldo M. Palharespag.16 Fund. Controle Robusto via Otimizacao Bloco 2
Funcoes Convexas
Definicao Considere um conjunto convexo C. f : C 7 R e denominada uma funcao
convexa se x1, x2 C e [0, 1]
f(x1 + (1 )x2) f(x1) + (1 )f(x2)
Considerando desigualdade estrita, entao f e estritamente convexa
f e concava se f e convexa
f(x1)
f(x2)
x1 x2
f(x1) + (1 )f(x2)
cReinaldo M. Palharespag.17 Fund. Controle Robusto via Otimizacao Bloco 2
Funcoes Convexas
Definicao Considere um conjunto convexo C. f : C 7 R e denominada uma funcao
quasi-convexa se x1, x2 C e (0, 1)
f(x1 + (1 )x2) max{f(x1), f(x2)}
Teorema Se f : C1 7 R e g : C2 7 R sao convexas sobre os conjuntos convexos C1
e C2 entao
1. f e convexa em C1, 0
2. f + g e convexa em C1TC2
Teorema C e f : C 7 R convexos.
f
Xk
kxk
!Xk
kf(xk), xk C, k 0,Xk
k = 1
cReinaldo M. Palharespag.18 Fund. Controle Robusto via Otimizacao Bloco 2
Mnimo de Funcao Convexa
Teorema Considere um conjunto convexo nao-vazio C X e f : C 7 R uma funcao
convexa. Entao
1. f e contnua no int{C}
2. O conjunto C C no qual f atinge seu mnimo e convexo
3. Qualquer mnimo local e tambem mnimo global de f
Dem. 3) Suponha que x C e um mnimo local de f e que x C tal que
f(x) < f(x). Sobre o seguimento x + (1 )x , 0 < < 1, obtem-se
f (x + (1 )x) = f (x + (x x)) f(x)+ (f(x) f(x))| {z }
Teoremas de Funcoes Convexas
Teorema Considere f C1. Entao f e convexa sobre um conjunto convexo C sse
f(x) f(y) +f(y)T (x y), x, y C
onde f(y) = {f/yi}, i = 1, . . . , n e o vetor gradiente
f
f(y)f(y) +f(y)T (x y)
xy
Teorema Considere f C2. Entao f e convexa sobre um conjunto convexo C sse
2f(x) < 0, em C. Onde 2f(x) =
2f
xixj
ff, i, j = 1, . . . , n e a matriz
Hessiana
cReinaldo M. Palharespag.20 Fund. Controle Robusto via Otimizacao Bloco 2
Teoremas de Funcoes Convexas
Teorema Considere f C1, uma funcao convexa sobre o conjunto convexo
nao-vazio C. Se existe um ponto x C tal que
f(x)T (x x) 0, x C
entao x e um mnimo global de f em C
Se f for estritamente convexa, ie
f(x) > f(y) +f(y)T (x y), x, y C, x 6= y
entao x C, tal que f(x)T (x x) > 0 e um mnimo global estrito de f em C
cReinaldo M. Palharespag.21 Fund. Controle Robusto via Otimizacao Bloco 2
Conjunto Poliedral
Definicao A interseccao de um numero finito de subespacos fechados e denominado
conjunto poliedral
Exemplo C ,x | Ax y, x Rn , y Rm , A Rmn
Nota Conjuntos poliedrais sao convexos e fechados, mas podem nao ser limitados
Definicao Um conjunto poliedral limitado e denominado politopo
Em outras palavras, um politopo e a casca convexa de um conjunto finito de vertices
Portanto todo elemento no politopo pode ser gerado pela combinacao convexa dos seus
vertices
cReinaldo M. Palharespag.22 Fund. Controle Robusto via Otimizacao Bloco 2
Desigualdades Matriciais Lineares LMIs
Denomina-se uma desigualdade matricial linear (LMI) em x a descricao:
A(x) = x1A1 + x2A2 + + xnAn B
onde B,Ai Sn =
X Rnn | X = XT
, i = 1, . . . , n
Note a grande similaridade com uma desigualdade linear,
aT x = x1a1 + x2a2 + + xpap b, b, ai R
Nota O conjunto solucao de uma LMI, ie {x Rn | A(x) B} e convexo
Por que? Definindo-se uma funcao afim f : Rn 7 Sn , da forma
f(x) = B A(x), entao {x | f(x) C Sn} = {x Rn | B A(x) Sn} e
a imagem inversa do cone das matrizes semi-definidas positivas, que e convexo...
Nota A imagem e {f(x) | x C Rn}...
cReinaldo M. Palharespag.23 Fund. Controle Robusto via Otimizacao Bloco 2
Politopo
Exemplo Politopo: P = co{v1, v2, . . . , v5}
v1
v2
v3
v4
v5
p1
p2
Todo p P e escrito da forma: p =P5
i=1ivi, i 0,
P5i=1
i = 1
Da figura,
p1 =1
2v1 +
1
2v2 + 0v3 + 0v4 + 0v5
p2 =1
3v1 +
1
3v2 + 0v3 +
1
3v4 + 0v5
p2 =1
3v4 +
2
3p1
cReinaldo M. Palharespag.24 Fund. Controle Robusto via Otimizacao Bloco 2
Um problema de otimizacao padrao
minx
x2 =h0 1
i 24x1x2
35 = cT x
s.a
8>>>: 1
2x1 + x2 6
x1 + 0x2 4 ,
0x1 + x2 1
8