Análise Convexapalhares/bloco2_ftcr.pdf · Análise Convexa Defini¸cão Um conjunto C é dito ser afim se a reta que passa por dois pontos distintos quaisquer em C está

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. Exercıcios

c©Reinaldo 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


Analise Convexa

Generalizacao Se C e um conjunto afim, p1, p2, . . . , pj ∈ C, e

jX

k=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

ff

e 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


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 ∈ Rm×n , 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.


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

jX

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


Conjuntos Convexos

Exemplo Um conjunto elipsoidal da forma

C =

p

˛˛˛˛

(p − pc)T P −1 (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 ∈T

nCn 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 ∈T

nCn


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)


Vertices

Fato A combinacao convexa pode ser generalizada para n pontos em C

p =nX

i=1

αipi, αi ≥ 0 enX

i=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


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?


Cones

3. Conjunto das matrizes simetricas semidefinidas positivas

Sn� = {A ∈ Rn×n | A = AT , A � 0}

e um cone convexo: se α1, α2 ≥ 0 e B, C ∈ Sn� , entao α1B + α2C ∈ Sn

�

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 = xT α1Bx + xT α2Cx ≥ 0

se B � 0, C � 0, α1, α2 ≥ 0


Hiperplanos ou Funcoes Afins

Definicao Denomina-se um hiperplano em X um conjunto

H =n

x ∈ X | pT x = b, 0 6= p ∈ X , b ∈ Ro

e p ⊥ H . Naturalmente a funcao afim pT x − b e nula em X

Para X = R2 e b = 1, se pT =h

1 1i

e H e o conjunto dos x ∈ R2 tal que gera-se

a reta na figura abaixo

〈p, x〉 = 1p

x

x

x

1

1


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 − α)pT x2 = αb + (1 − α)b = b

Um hiperplano divide o espaco em dois semi-espacos fechados:

H≤ =n

x ∈ X | pT x ≤ bo

e H≥ =n

x ∈ X | pT x ≥ bo

H≥ e o semi-espaco na direcao de p e H≤ na direcao de −p. Estes semi-espacos sao

convexos, porem nao-afins


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}


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≥


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∗


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>

C1

C1C1

C2

C2

C2H

H

H

+ Exemplo Se C1 = C2 = {0} ⊆ R, entao o hiperplano x = 0 separa C1 e C2


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)


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 C1

TC2

Teorema C e f : C 7→ R convexos.

f

X

k

αkxk

!

≤X

k

αkf(xk), xk ∈ C, αk ≥ 0,X

k

αk = 1


Mınimo de Funcao Convexa

Teorema Considere um conjunto convexo nao-vazio C ⊂ X e f : C 7→ R uma funcao

convexa. Entao

1. f e contınua no int{C}

2. O conjunto C ⊂ C no qual f atinge seu mınimo e convexo

3. Qualquer mınimo local e tambem mınimo global de f

Dem. 3) Suponha que x∗ ∈ C e um mınimo 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 }

<0

< f(x∗)

o que contradiz, para α → 0+, que x∗ e um mınimo local


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

∂xi∂xj

ff

, i, j = 1, . . . , n e a matriz

Hessiana


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 mınimo 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 mınimo global estrito de f em C


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 ∈ Rm×n

¯

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


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 ∈ Rn×n | 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}...


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=1αivi, αi ≥ 0,

P5

i=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


Um problema de otimizacao padrao

minx

x2 =h

0 1i

2

4x1

x2

3

5 = cT x

s.a

8

>><

>>:

− 1

2x1 + x2 ≥ 6

x1 + 0x2 ≥ 4 ,

0x1 + x2 ≥ 1

8

<

:

x1 + 0x2 ≤ 8

0x1 + x2 ≤ 5

x1

x2

0

1

4

5

6

8 12


Estendendo os conceitos

Suponha que a matriz A ∈ P onde P e um politopo, ie P = co{A1, A2, . . . , Aκ}

em outras palavras P ,˘A | A =

Pκ

i=1αiAi, αi ≥ 0,

Pκ

i=1αi = 1

¯

Entao para o problema de otimizacao:

minX

Traco{X}

s.a X ∈ Ri, i = 1, . . . , κ

sendo Ri ,n

X | AiXBC + (AiXBC)T + Q 4 0, Q = QT , ∃C−1o

Geram-se κ restricoes sendo que os vertices do politopo sao elementos matricias !!


Exercitando a fe ...

Exercıcio 1. Mostre que qualquer norma e uma funcao convexa.

Exercıcio 2. Considere um escalar nao-negativo, λ, e define-se o seguinte conjunto:

K = {A = AT ∈ Rn×n | A < λI}

Suponha que A ∈ B{K} onde B{·} denota a fronteira de um conjunto {·}.

1. Caracterize o espectro de A


... e concretizando-a

Exercıcio 3. Considere uma matrix positiva semi-definida Y ∈ Cn×n . Mostre que o

conjunto˘X ∈ Cn×n | X < Y

¯e um cone convexo em Cn×n . (Dica: mostre que o

conjunto e convexo para entao mostrar que e um cone)

Exercıcio 4. Mostre que o problema de otimizacao a seguir e convexo:

minP

Traco{P }

s.a P ∈ L

onde L ,˘P | AT P + P A ≺ 0, P = P T , P ∈ Rn×n , A ∈ Rn×n

¯


Documents

Análise Convexapalhares/bloco2_ftcr.pdf · Análise Convexa Defini¸cão Um conjunto C é dito ser afim se a reta que passa por dois pontos distintos quaisquer em C está