Programação não-linear

c

PAVF

1

Convexidade

Conjuntos e func~es convexas o Hiperplanos e semi-espacos Hiperplanos suportes e separadores Teorema da separac~o a Func~es convexas diferenciaveis o

c

PAVF

2

Conjuntos e func~es convexas o Conjunto convexo
Rn e um conjunto convexo se para quaisquer x y 2 e qualquer 2 0 1], x + (1 ; )y 2

convexo

n~o-convexo a

Exemplos Teorema

Rn, subespacos, variedades
, conjunto vazio

Sejam ; conjuntos convexos do Rn. Ent~o tambem s~o a a conjuntos convexos 1. := fy : y = x x 2 g 2 R 2. + ; 3. \ ;

c

PAVF

3

Conjuntos e func~es convexas o Casca convexa
Rn. A casca convexa de , representada como conv ( ), e o menor conjunto convexo que contem
Seja

conv

Combinac~o convexa a
Sejam x1 x2 : : : xp elementos de forma

Rn. Elementos da
+ pxp

x= com p X

i=1

ix

i=

1

x1 + 2x2 + n X

0 i = 1 2 ::: n e a o i i = 1, s~o combinac~es i=1 convexas dos elementos x1 x2 : : : xp 2

x2 x1 x3

c

PAVF

4

Conjuntos e func~es convexas o Ponto extremo
Diz-se que z 2 Rn e um ponto extremo de se n~o a existem x y 2 x 6= y tais que z = x +(1 ; )y para algum
2 (0

1)

Teorema
Qualquer conjunto Rn convexo e compacto e a casca convexa dos seus pontos extremos

Exemplo (Casca convexa)
Seja

R2 de nido como
:= f(;1 0)g f(x1 x2) : x2 + x2 = 1 x1 0g 1 2 x2

conv ( )
;1

0

x1

c

PAVF

5

Conjuntos e func~es convexas o Cone
Diz-se que Rn e um cone (com vertice na origem) se x 2 implica que x 2 para todo 0

Exemplos
a) := f(x1 x2) 2 R2 : x1x2 0g b) Subespacos e variedades do Rn c) Conjunto dos vetores n~o-negativos: a
:= fx 2 Rn : xi 0 i = 1 2 : : : ng

Cone gerado
O cone gerado por vetores x y 2 Rn e de nido como

:= fz 2 Rn : z = x + y

0

0g

c

PAVF

6

Conjuntos e func~es convexas o x z

y

x y : raios extremos do cone

Cone polar
O cone polar associado a qualquer conjunto

:= fy 2 Rn : yT x 0 x 2

Rn e

g