Otimização/Conjuntos convexos

Esta página é um esboço de matemática. Ampliando-a você ajudará a melhorar o Wikilivros.

Intersecção de conjuntos convexos é convexo

Sejam $D_{j} \subset ℝ^{n}, j \in I_{n},$ conjuntos convexos, onde $I_{n} = {k \in ℕ / 1 \leq k \leq n, n \in ℕ}$

Seja $D = \cap_{j \in I_{n}} D_{j}$ . Para quaisquer $x, y \in D$ temos que $x, y \in D_{j}$ para qualquer $j \in I_{n}$ .

Como todo $D_{j}$ é convexo, para quaisquer $j \in I_{n}$ e $λ \in [0, 1]$ , $λ x + (1 - λ) y \in D_{j} ⟹ λ x + (1 - λ) y \in D$

Conjunto Poliedral

Definição

Um conjunto é poliedral se é a intersecção finita de hiperplanos e semi-espaços

Um conjunto poliedral em $ℝ^{n}$ é convexo

O fecho e o interior de um conjunto convexo são convexos

A soma de convexos fechados é convexo e fechado

Sejam $D_{j} \subset ℝ^{n}, j = 1, 2$ , conjuntos convexos e fechados. Um deles é limitado.

Mostrar que $\sum_{i = 1}^{2} D_{j}$ é um conjunto convexo e fechado

Combinação convexa de p pontos

Definição

Seja $x^{i} \in ℝ^{n}, α_{i} \in [0, 1], i = 1, ..., p; \sum_{i = 1}^{p} α_{i} = 1$ . A combinação convexa dos $x^{i} \in ℝ^{n}$ é o ponto $\sum_{i = 1}^{p} α_{i} \cdot x^{i}$

Teorema da combinação convexa

Um conjunto $D \in ℝ^{n}$ é convexo se, e somente se, a combinação convexa $\sum_{i = 1}^{p} α_{i} x_{i} \in D$ , $\forall p \in ℕ, x^{i} \in D \land α_{i} \in [0, 1], i = 1, ..., p; \sum_{i = 1}^{p} α_{i} = 1$ ,

Desigualdade de Jensen

Sejam $D \subset ℝ^{n}$ um conjunto convexo e $f : D \to ℝ$ uma função convexa, $\forall p \in ℕ, x^{i} \in D \land α_{i} \in ℝ_{+}, i = 1, ..., p; \sum_{i = 1}^{p} α_{i} = 1$

Mostrar que $f (\sum_{i = 1}^{p} α_{i} x_{i}) \leq \sum_{i = 1}^{p} α_{i} f (x_{i})$

Teorema de Carathéodory

Seja $x \in ℝ^{n}$ uma combinação convexa de pontos do conjunto $D \subset ℝ^{n}$ .

Mostrar que $\exists x_{i} \in D \land α_{i} \in ℝ_{+}, i = 1, ..., n + 1; x = \sum_{i = 1}^{n + 1} α_{i} x_{i}, \sum_{i = 1}^{n + 1} α_{i} = 1$

Fecho convexo

Definição

O fecho convexa de um conjunto qualquer D é o menor conjunto convexo que contem D e simbolizado por conv D.

Definição

O conjunto de todas as combinações convexas de pontos de D, simbolizaremos por $c o m b D = {x \in ℝ^{n}; x = \sum_{i = 1}^{n + 1} α_{i} x_{i}, \sum_{i = 1}^{n + 1} α_{i} = 1, x_{i} \in D \land α_{i} \in ℝ_{+}, i = 1, ..., p; p \in ℕ}$ .

Corolário de um fecho convexo

Se $D \subset ℝ^{n}$

Mostrar que conv D = comb D

Corolário da compacidade do conv D

Seja $D \subset ℝ^{n}$ compacto

Mostrar que conv D é compacto