PAVF

c

1999 19

Fundamentos matem�aticos

� Conjuntos

� Conjuntos convexos

� Cones, hiperplanos, poliedros, politopos

� Fun�c~oes convexas

� M��nimos locais e globais

� Condi�c~oes de Kuhn-Tucker

PAVF

c

1999 20

Conjuntos

De�ni�c~ao - Conjunto

Agrega�c~ao de objetos

Caracteriza�c~oes

� enumerando-se os seus elementos:

Bandeira := fverde;amarelo;azul;brancog

� evidenciando-se propriedades:

C��rculo := f(x

1

; x

2

) : x

2

1

+ x

2

2

� r

2

g (r=raio)

Estados l�ogicos

Dados um elemento x e um conjunto C quaisquer

x 2 C : x pertence a C

x 62 C : x n~ao pertence a C

Fun�c~ao caracter��stica: �

C

: X ! f0; 1g

�

C

(x) =

8

<

:

1; se x 2 C

0; se x 62 C

X : conjunto onde x est�a de�nido

PAVF

c

1999 21

Conjuntos

Opera�c~oes alg�ebricas

Dados dois conjuntos A;B quaisquer,

Uni~ao

A [ B := fx : x 2 A ou x 2 Ag

Interse�c~ao

A \ B := fx : x 2 A e x 2 Ag

Complemento

A := fx : x 62 Ag

Subconjunto

S �e um subconjunto de C se

x 2 S ) x 2 C

Nota�c~ao: S � C

PAVF

c

1999 22

Conjuntos

Produto carteziano

X � Y := f(x; y) : x 2 X ; y 2 Yg

� adi�c~ao e multiplica�c~ao por escalar em X � Y de�nidas

como

(x

1

; y

1

) + (x

2

; y

2

) := (x

1

+ x

2

; y

1

+ y

2

)

�(x; y) := (�x; �y); � escalar

R

n

= R�R� � � � �R (n vezes)

� conjunto dos vetores de n componentes reais. No-

ta�c~ao: x := (x

1

; x

2

; : : : ; x

n

); x

i

2 R

� soma e multiplica�c~ao: se x; y 2 R

n

ent~ao

x+ y := (x

1

+ y

1

; x

2

+ y

2

; : : : ; x

n

+ y

n

)

�x := (�x

1

; �x

2

; : : : ; �x

n

); � 2 R

� vetor nulo: 0 := (0; 0; : : : ; 0)

� forma matricial: vetor-coluna

x =

2

6

6

6

6

6

6

4

x

1

x

2

.

.

.

x

n

3

7

7

7

7

7

7

5

PAVF

c

1999 23

Conjuntos

Compara�c~oes ordinais

� se x; y 2 R

n

s~ao vetores quaisquer, ent~ao

x = y se e somente se x

i

= y

i

; i = 1; 2; : : : ; n

x � y se e somente se x

i

� y

i

; i = 1; 2; : : : ; n

x < y se e somente se x

i

< y

i

; i = 1; 2; : : : ; n

� se x � y e x 6= y, ent~ao x

j

< y

j

para pelo menos

uma componente j 2 f1; 2; : : : ; ng

� nem todos os vetores do R

n

s~ao compar�aveis no sen-

tido ' � '

� R

n

�e um conjunto parcialmente ordenado, de acordo

com a rela�c~ao de ordem ' � '

Opera�c~oes matriciais

x+ y =

2

6

6

6

6

6

6

4

x

1

+ y

1

x

2

+ y

2

.

.

.

x

n

+ y

n

3

7

7

7

7

7

7

5

; �x =

2

6

6

6

6

6

6

4

�x

1

�x

2

.

.

.

�x

n

3

7

7

7

7

7

7

5

; � 2 R

PAVF

c

1999 24

Conjuntos convexos

De�ni�c~ao - Conjunto convexo

C �e um conjunto convexo se para quaisquer x; y 2 C

�x+ (1� �)y 2 C; 8� 2 [0; 1]

PSfrag replacements

x

x

y

y

Convexo N~ao-convexo

Propriedades

Dados dois conjuntos convexos X e Y , s~ao tamb�em

conjuntos convexos

a) X \ Y

b) X + Y := fz : z = x+ y; x 2 X ; y 2 Yg

c) �X := fz : z = �x; x 2 Xg; � 2 R

De�ni�c~ao - Casca convexa

A casca convexa de um conjunto qualquer C, denota-

da como conv (C), �e a interse�c~ao de todos os conjuntos

convexos que contem C

PAVF

c

1999 25

Conjuntos convexos

PSfrag replacements

C

conv (C)

De�ni�c~ao - Cone

C �e um cone (com v�ertice na origem) se x 2 C implica

que �x 2 C; 8� � 0

� Exemplos no plano x

1

� x

2

:

PSfrag replacements

00 x

1

x

1

x

2

x

2

C

1

:= f(x

1

; x

2

) : x

1

x

2

� 0g C

2

:= f(x

1

; x

2

) : x

1

� 0; x

2

� 0g

De�ni�c~ao - Cone gerado

O cone gerado pelos vetores x; y 2 R

n

�e o conjunto

de�nido por

C := fz : z = �x+ �y; � � 0; � � 0g

PAVF

c

1999 26

Cones, hiperplanos, poliedros, politopos

PSfrag replacements

0

x

1

x

2

x

y

z

C

x; y : raios extremos do cone C

De�ni�c~ao - Cone polar

O cone polar associado associado a um conjunto qual-

quer C �e

C

�

:= fy : y

T

x � 0; x 2 Cg

Interpreta�c~ao no plano:

PSfrag replacements

x

y

C

C

�

PAVF

c

1999 27

Cones, hiperplanos, poliedros, politopos

De�ni�c~ao - Hiperplano

Seja c 2 R

n

; c 6= 0 e � 2 R quaisquer. O conjunto

H := fx : c

T

x = �g

representa um hiperplano do R

n

. Cada hiperplano carac-

teriza dois semi-espa�cos fechados

H

�

:= fx : c

T

x � �g; H

�

:= fx : c

T

x � �g

e dois semi-espa�cos abertos

H

>

:= fx : c

T

x > �g; H

<

:= fx : c

T

x < �g

De�ni�c~ao - Poliedro e politopo

A interse�c~ao de um no. �nito de semi-espa�cos fechados

determina um poliedro. Um poliedro limitado �e chamado

de politopo

PSfrag replacements

Poliedro Politopo

PAVF

c

1999 28

Fun�c~oes convexas

De�ni�c~ao - Fun�c~ao convexa

f �e uma fun�c~ao convexa sobre um conjunto convexo C

se para quaisquer x

1

; x

2

2 C e qualquer � 2 [0; 1]

f(�x

1

+ (1� �)x

2

) � �f(x

1

) + (1� �)f(x

2

)

Interpreta�c~ao no plano:

PSfrag replacements

x

�x

1

+ (1� �)x

2

�f(x

1

) + (1� �)f(x

2

)

f(�x

1

+ (1� �)x

2

)

0

x

1

x

2

f(x

1

)

f(x

2

)

f(x)

� Se para quaisquer x

1

; x

2

2 C; x

1

6= x

2

e qualquer

� 2 (0; 1) a desigualdade �e estrita, f �e uma fun�c~ao

estritamente convexa

� f �e uma fun�c~ao (estritamente) concava sobre um con-

junto convexo C se �f for uma fun�c~ao (estritamente)

convexa sobre C

PAVF

c

1999 29

Fun�c~oes convexas

Propriedades

Se f �e uma fun�c~ao convexa sobre C convexo e f possui

primeiras derivadas parciais cont��nuas, ent~ao

f(x

2

) � f(x

1

) +rf(x

1

)

T

(x

2

� x

1

); 8x

1

; x

2

2 C

onde

rf(x

1

) :=

2

6

6

6

6

6

6

4

@f(x

1

)=@x

1

@f(x

1

)=@x

2

.

.

.

@f(x

1

)=@x

n

)

3

7

7

7

7

7

7

5

: gradiente de f em x

1

Se f �e convexa sobre C, possui segundas derivadas par-

ciais cont��nuas e

F (x) := f@

2

f(x)=@x

i

x

j

g

�e a matriz hessiana de f em x, ent~ao

F (x) � 0; 8x 2 C

isto �e, para todo x 2 C,

y

T

F (x)y � 0; 8 y 2 R

n

PAVF

c

1999 30

Fun�c~oes convexas

Propriedades

Sejam f; g fun�c~oes convexas de�nidas sobre conjuntos

convexos C e S, respectivamente. Ent~ao

a) �f �e convexa sobre C, qualquer que seja � � 0

b) f + g �e convexa sobre C \ S

De�ni�c~ao - Combina�c~ao convexa

A combina�c~ao convexa de m vetores fx

1

; x

2

; : : : ; x

m

g �e

de�nida como

�

1

x

1

+ �

2

x

2

+ � � �+ �

m

x

m

com �

i

� 0; i = 1; 2; : : : ;m e

m

X

i=1

�

i

= 1

Desigualdade de Jensen

Seja f uma fun�c~ao convexa sobre C convexo e x

1

; x

2

; : : : ; x

m

elementos quaisquer de C. Ent~ao

f

0

@

m

X

i=1

�

i

x

i

1

A

�

m

X

i=1

�

i

f(x

i

)

para todos �

i

� 0; i = 1; 2; : : : ;m com

m

X

i=1

�

i

= 1

PAVF

c

1999 31

Fun�c~oes convexas

Teorema

Seja f uma fun�c~ao convexa sobre C convexo. Ent~ao o

conjunto

C

�

:= fx 2 C : f(x) � �g

�e convexo para todo � 2 R

A convexidade de f sobre C �e uma condi�c~ao su�ciente para

a convexidade de C

�

; 8 � 2 R:

PSfrag replacements

x0

f(x)

C

�

�

[f; C]

Teorema (Condi�c~ao Necess�aria e Su�ciente)

C

�

�e convexo para todo � 2 R se e somente se f �e

quasi-convexa sobre C convexo, isto �e, se para quaisquer

x

1

; x

2

2 C e qualquer � 2 [0; 1],

f(�x

1

+ (1� �)x

2

) � maxff(x

1

); f(x

2

)g

PAVF

c

1999 32

Fun�c~oes convexas

De�ni�c~ao - Ep��grafo

O ep��grafo de uma fun�c~ao �e o conjunto de�nido por

[f; C] := f(x; �) : f(x) � �; x 2 C; � 2 Rg

Teorema

Uma fun�c~ao f de�nida sobre C convexo �e convexa se e

somente se [f; C] �e um conjunto convexo

De�ni�c~ao - Hiperplano suporte

H �e um hiperplano suporte de um conjunto convexo C

se C � H

�

ou C � H

�

e H cont�em um ponto de cls (C)

PSfrag replacements

x 2 cls (C)

H

C

Teorema

Se x

0

62 int (C) e int (C) 6= ;, ent~ao existe um hiperpla-

no H tal que x

0

2 H e C � H

�

ou C � H

�

PAVF

c

1999 33

Fun�c~oes convexas

Teorema

Seja C um conjunto convexo e f uma fun�c~ao convexa

sobre C. Ent~ao para cada x

0

2 int (C) existe um vetor �

tal que

H := f(x; y) : y = f(x

0

) + �

T

(x� x

0

)g

�e um hiperplano suporte de [f; C] no ponto (x

0

; f(x

0

))

� � �e um subgradiente de f no ponto x = x

0

, isto �e,

satisfaz a desigualdade

f(x) � f(x

0

) + �

T

(x� x

0

); 8x 2 C

� se f for diferenci�avel, ent~ao o �unico subgradiente de

f em x = x

0

�e � = r f(x

0

)

PSfrag replacements

0 x

x

0

f(x

0

)

H

[f; C]

c =

"

�

�1

#

PAVF

c

1999 34

M��nimos locais e globais

De�ni�c~ao - M��nimo local

Seja f uma fun�c~ao de�nida sobre um conjunto . Um

ponto x

�

2 �e um m��nimo local de f sobre se existe

� > 0 tal que

f(x

�

) � f(x); 8x 2 \ B(x

�

; �)

onde B(x

�

; �) := fx : kx � x

�

k < �g; x

�

2 �e um

m��nimo local estrito de f sobre se f(x

�

) < f(x); 8x 2

\ B(x

�

; �); x 6= x

�

De�ni�c~ao - M��nimo global

Seja f uma fun�c~ao de�nida sobre um conjunto . Um

ponto x

�

2 �e um m��nimo global de f sobre se

f(x

�

) � f(x); 8x 2

x

�

2 �e um m��nimo global estrito de f sobre se

f(x

�

) < f(x); 8x 2 ; x 6= x

�

� O ordenamento completo de R (imagem de f) de acordo

com '�' viabiliza as de�ni�c~oes acima

PAVF

c

1999 35

M��nimos locais e globais

Teorema

Seja f uma fun�c~ao convexa sobre convexo. Ent~ao o

conjunto � � no qual f atinge seu m��nimo �e convexo e

todo m��nimo local de f �e tamb�em um m��nimo global

Prova:

� Assuma � := fx 2 : f(x) � c

0

g, onde c

0

=

min

x2

f(x). Ent~ao � �e um conjunto convexo, pois f �e

convexa sobre convexo

� Assuma que x

�

2 �e um m��nimo local de f , mas

que existe x 2 tal que f(x) < f(x

�

). Ent~ao, para

0 < � < 1,

f(x

�

+�(x�x

�

)) � f(x

�

)+�(f(x)�f(x

�

)) < f(x

�

)

o que contradiz (para � ! 0

+

) que x

�

�e um m��nimo

local 2

Teorema

Seja f uma fun�c~ao convexa diferenci�avel sobre con-

vexo. Se existe um ponto x

�

2 tal que

rf(x

�

)

T

(x� x

�

) � 0; 8x 2

ent~ao x

�

�e um m��nimo global de f sobre

PAVF

c

1999 36

Condi�c~oes de Kuhn-Tucker

Teorema

Seja f uma fun�c~ao diferenci�avel. Se x

�

�e um m��nimo

local de f sobre o R

n

, ent~ao

r f(x

�

) = 0

De�ni�c~ao - Ponto regular

Seja := fx : g

i

(x) � 0; i = 1; 2; : : : ; pg um conjun-

to de restri�c~oes. Ent~ao x

�

�e um ponto regular das restri�c~oes

se os gradientes das restri�c~oes ativas em x

�

(g

i

(x

�

) = 0)

s~ao linearmente independentes

Teorema - Condi�c~oes de Kuhn-Tucker

Sejam f; g

1

; g

2

; : : : ; g

p

fun�c~oes diferenci�aveis. Se x

�

�e

um m��nimo local de f restrito a := fx : g(x) � 0g e

um ponto regular das restri�c~oes, ent~ao existem reais �

i

�

0; i = 1; 2; : : : ; p tais que

rf(x

�

) +

p

X

i=1

�

i

rg

i

(x

�

) = 0

g

i

(x

�

) � 0; �

i

g

i

(x

�

) = 0; i = 1; 2; : : : ; p

� Se f �e convexa sobre convexo e x

�

�e um ponto regular,

ent~ao x

�

�e um m��nimo local (global) de f sobre se e

somente se x

�

satisfaz as condi�c~oes de Kuhn-Tucker