Otimização/Métodos de penalidades

Origem: Wikilivros, livros abertos por um mundo aberto.

< Otimização

Ir para: navegação, pesquisa

Otimização

A Wikipédia tem mais sobre este assunto:

Métodos de penalidades

Os métodos que recebem este nome fazem parte de uma família de métodos baseados em:

Simplicidade conceitual;
Eficiência prática;

Algumas das primeiras funções de penalidade foram desenvolvidas por:

Courant (1943)
Ablate Brighham (1955) (qual o artigo?)
AV Fiacco, GP McCormick (1968) (qual o artigo?)

Para compreender este tipo de método, será considerado o seguinte problema:

$(P) \left\{\begin{matrix} min f(x)\\ g_i(x)\le 0 \forall i = 1, \ldots, p\\ h_i(x) = 0 \forall j = 1, \ldots, q \end{matrix}\right.$

Adicionalmente, se for considerado o conjunto de pontos $C = \{ x\in \mathbb{R}^n: g_i(x)\le 0, \forall i = 1, \ldots, p; h_i(x) = 0, \forall j = 1, \ldots, q\}$ , o problema (P) se escreve ainda como

$(P) \left\{\begin{matrix} min f(x)\\ x \in C \end{matrix}\right.$

Uma primeira idéia para a resolução desse tipo de problema é fazer uso de funções indicadoras, conforme é definido a seguir:

Definição

Dado um conjunto não vazio $C \subset \mathbb{R}^n$ , define-se a função indicadora $I_C:\mathbb{R}^n \mapsto \mathbb{R} \cup \{ \infty \}$ por:

$I_C(x) = \begin{cases} 0, & \mbox{se }x \in C\\ \infty, & \mbox{se }x\not\in C \end{cases}$

Notas: A função indicadora $I C$ é às vezes denotada por $χ C$ .

Para transformar um conjunto (P) em um problema sem restrições, pode-se proceder da seguinte maneira: Considerar o problema (PD), dado por:

$(PD) \left\{\begin{matrix} min f(x) + I_C(x)\\ x\in \mathbb{R}^n \end{matrix}\right.$

Considerando $i_C:\mathbb{R} \mapsto \mathbb{R} \cup \{ \infty \}$ definida por:

$i_C(t) = \begin{cases} 0, & \mbox{se } t\le 0\\ \infty, & \mbox{se } t > 0 \end{cases}$

Tem-se ainda o problema (PP), dado por:

$(PP) \left\{\begin{matrix} min f(x) + \sum_{i = 1}^{p} i(g_i(x)) + \sum_{j = 1}^{p} i(h_j(x))\\ x\in \mathbb{R}^n \end{matrix}\right.$

Comentários:

A grande vantagem desta idéia é que ela transforma um problema com restrições em um problema irrestrito.
A principal desvantagem é que a função $φ$ definida a seguir é descontínua em cada ponto $x \in \partial C$ :

$\phi:\mathbb{R}^n \mapsto \mathbb{R} \cup \{ \infty \}$

$\phi(x) = f(x) + \sum_{i = 1}^{p} i(g_i(x)) + \sum_{j = 1}^{p} i(h_j(x))$

[editar] Método de penalidade exterior

Para contornar a desvantagem da descontinuidade da função apresentada anteriormente, surgem outras funções, como por exemplo:

Gráfico de uma função de penalidade

$H:\mathbb{R} \mapsto \mathbb{R}$

$H(t) = \begin{cases} 0, & \mbox{se } t\le 0\\ t^2, & \mbox{se } t > 0 \end{cases}$

Definição

Dada uma função $g:A \mapsto \mathbb{R}$ , definida em um conjunto arbitrário $A$ , define-se a parte positiva de $g$ , como:

g + (x) = m a x {0, g (x)}

Um dos autores deste material sugeriu a adição de uma imagem para comparar uma função

g (x)

e sua correspondente

g + (x) = m a x {0, g (x)}

.

Exercício

Verifique que para cada $x \in \mathbb{R}^n$ tem-se, para cada $i$ , a igualdade $H(g_i(x)) = \left(g_i^+(x) \right)^2$ , onde $g_i^+$ é a parte positiva de $g i$ e $H$ é a função definida no exemplo anterior.

Resolução

De fato, dada qualquer função $g:A \mapsto \mathbb{R}$ , segue da própria definição de

H

que

$H(g(x)) = \begin{cases} 0, & \mbox{se } g(x)\le 0\\ g(x)^2, & \mbox{se } g(x) > 0 \end{cases}$

Mas

$g^+(x) = max \{0, g(x) \} = \begin{cases} 0, & \mbox{se } g(x)\le 0\\ g(x), & \mbox{se } g(x) > 0 \end{cases}$

implica que

$(g^+(x))^2 = max \{0, g(x) \} = \begin{cases} 0, & \mbox{se } g(x)\le 0\\ (g(x))^2, & \mbox{se } g(x) > 0 \end{cases}$

Portanto, $H(g(x)) = \left(g^+(x) \right)^2$ . Como $g$ pode ser tomada arbitrariamente, tem-se em particular que $H(g_i(x)) = \left(g_i^+(x) \right)^2$ .

Exercício

Verifique que para cada $x \in \mathbb{R}^n$ tem-se, para cada $j$ , a igualdade $H\left(h_j(x)^2\right) = \left(h_j(x) \right)^2$ .

Um dos autores deste material sugeriu conferir o enunciado do exercício anterior. A afirmação parece ser falsa nos casos em que

h j (x) < 0

.

A idéia de aplicar penalizações aos pontos que não pertencem ao conjunto viável é formalizada na seguinte definição:

Definição

Seja $H:\mathbb{R}^n \mapsto \mathbb{R}$ . A função $H$ é chamada de função de penalidade exterior se possui as seguintes propriedades:

$H(x) \ge 0, \forall x \in \mathbb{R}^n$
$H(x) = 0, \Leftrightarrow x \in C$
$H$ é contínua

Nota: Lembre-se que $C = \{ x\in \mathbb{R}^n: g_i(x)\le 0, \forall i = 1, \ldots, p; h_i(x) = 0, \forall j = 1, \ldots, q\}$ é o conjunto viável do problema (P).

Em particular, as funções $H \circ g_i$ são funções de penalidade exterior.

Definição

Seja $\theta:\mathbb{R}^n \mapsto \mathbb{R}$ . A função $θ$ é dita coerciva se $\lim_{\| x \| \to \infty}\theta(x) = +\infty$

Um dos autores deste material sugeriu a adição de exemplos de funções de penalidade, juntamente com algumas imagens ilustrando os seus gráficos.

Nota: Conforme o dicionário on-line, disponibilizado pela empresa Priberam, o termo coercivo significa: que coage; que reprime; que impõe pena; coercitivo. Nesse sentido, esse é um termo adequado ao tratar do conceito anterior, no contexto dos métodos de penalidade.

Exercício

Verifique que $θ$ é uma função coerciva se, e somente se, $L_\theta (\lambda) = \{ x \in \mathbb{R}^n : \theta (x) \le \lambda \}$ é limitado para todo $\lambda \in \mathbb{R}$ .

Resolução

Pela definição de limite, a afirmação

$\lim_{\| x \| \to \infty}\theta(x) = +\infty$

é equivalente a dizer que

$\forall K > 0, \exists M >0$ tal que $\forall x$ tem-se $\|x\|>M \Rightarrow \theta(x)>K$ .

Esta última implicação, é equivalente à

$\theta(x)\le K \Rightarrow \|x\| \le M$ (sua contrapositiva).

Pela definição de conjunto de nível, isso equivale à $x \in L_\theta(K) \Rightarrow \|x\| \le M$ . A existência de um número $M$ com tal propriedade significa que $L θ (K)$ é um conjunto limitado, donde conclui-se a equivalência entre coercividade e limitação dos conjuntos de níveis

Um dos autores deste material sugeriu a adição de uma imagem que ilustre geometricamente a relação entre coercividade e conjuntos de nível.

Exercício

Verifique que $H:\mathbb{R}^n \mapsto \mathbb{R}$ definida por $H(x) = \sum_{i = 1}^{p}\left( g_i^+(x)\right)^2 + \sum_{j = 1}^{q}\left( h_j(x)\right)^2$ é uma função de penalidade exterior, onde conforme anteriormente, $g_i^+$ é a parte positiva de $g i$ .

Resolução

Primeiramente,

H (x)

é uma função não negativa, pois o quadrado de qualquer número real é não negativo, assim como a soma de números reais não negativos.

Em segundo lugar, tem-se $H (x) = 0$ se, e somente se, para cada índice $i$ e cada índice $j$ vale $g_i^+(x) = 0$ e $h j (x) = 0$ . Como $g_i^+(x) = 0 \Leftrightarrow g_i \le 0$ , tem-se $H(x)=0 \Leftrightarrow x \in C$

Finalmente, como a soma e o produto de funções contínuas resulta em uma função contínua, segue que $H (x)$ é contínua, pois $g i, h j$ são contínuas.

Exercício

Verifique que se $g: \mathbb{R}^n \mapsto \mathbb{R}$ é uma função contínua coerciva, então existe $\bar{x} \in \mathbb{R}^n$ tal que $g(\bar{x}) \le g(x), \forall x \in \mathbb{R}^n$ .

Resolução

Considere um ponto arbitrário $\hat{x} \in \mathbb{R}^n$ . Tome $\lambda = g(\hat{x})$ . Nestas condições,

L g (λ)

é limitado (conforme um dos exercícios anteriores) e fechado (pois é pré-imagem de um conjunto fechado por uma função contínua), portanto compacto. Neste caso, conforme o teorema de Weierstrass, a função

g

possui algum ponto de mínimo no conjunto

L g (λ)

, ou seja, existe $\bar{x} \in L_g(\lambda)$ tal que $g(\bar{x}) \le g(x), \forall x \in L_g(\lambda)$ .

Ne verdade, tal ponto $\bar{x}$ é também um minimizador global da função $g$ , pois se $x \not\in L_g(\lambda)$ então $g (x) > λ$ (pela definição do conjunto $L g (λ)$ ).

Um dos autores deste material sugeriu a adição de uma imagem ilustrando a existência de minimizadores globais para funções coercivas.

[editar] Alguns conceitos da topologia

Em algumas situações, é interessante ter em mente que certos conceitos definidos no contexto da Otimização são, na verdade, instanciações de conceitos mais gerais, muitos deles provenientes da topologia. Alguns exemplos são apresentados a seguir.

Definição

Dado um conjunto $X$ , uma coleção $\Gamma \subset \mathcal{P}$ de subconjuntos de $X$ é chamada de topologia se:

$\emptyset, X \in \Gamma$
$\left\{ A_i \right\}_{i \in I} \subset \Gamma \Rightarrow \cup_{i \in I} A_i \in \Gamma$
$\left\{ B_i \right\}_{i =1}^p \subset \Gamma \Rightarrow \cap_{i =1}^p B_i \in \Gamma$

Exemplos

Topologia euclidiana:

X = R

$\Gamma = \Gamma_1 = \{ \emptyset \} \cup \{X\} \cup \left\{ A \subset \mathbb{R}: \forall x \in A, \exists \epsilon_x > 0, \left( x-\epsilon_x, x+\epsilon_x \right) \subset A \right\}$

Em outras palavras, a topologia euclideana é a coleção de todos os conjuntos abertos contidos em $\mathbb{R}$ . Pode-se verificar com facilidade que de fato são satizfeitas as três propriedades que definem uma topologia.

Outo exemplo muito comum é o seguinte:

Topologia euclideana extendida:

$X = R \cup \{ \infty \}$

$\Gamma = \Gamma_1 \cup \left\{ A \subset \mathbb{R} \cup \{ \infty \}: \exists a \in \mathbb{R}, A = \left] a, \infty \right]\right\}$

Em geral, a noção de limite seria caracterizada topologicamente da seguinte forma:

Definição

$\lim_{n \to \infty} x_n = a \Leftrightarrow \forall I \ni x, \exists n_0 \in \mathbb{N}, \forall n \ge n_0 \Rightarrow x_n \in I$

[editar] De volta ao método

Uma vez apresentados os conceitos iniciais, pode-se provar o seguinte teorema:

Teorema

Considere:

$H: \mathbb{R}^n \mapsto \mathbb{R}$ uma função de penalidade exterior;
$f: \mathbb{R} \mapsto \mathbb{R}$ uma função contínua;
$C = \{ x\in \mathbb{R}^n: g_i(x)\le 0, \forall i = 1, \ldots, p; h_i(x) = 0, \forall j = 1, \ldots, q\}$ um conjunto fechado;
$\left\{ r_k \right\}$ uma sequência de termos positivos tal que $\lim_{k \to \infty} r_k = 0$ .

Suponha que é válida uma das seguintes propriedades:

$f$ é coerciva.
$C$ é limitado e $H$ é coerciva.

Se, para cada

k

, for escolhido $\bar{x}(r_k) \in \arg \min \{ f(x) + \frac{1}{r_k}H(x)\}$ ,então:

$\left\{ \bar{x}(r_k) \right\}$ possui algum ponto de acumulação;
Todo ponto de acumulação de $\left\{ \bar{x}(r_k) \right\}$ é solução do problema (P);
$\lim_{k \to \infty} H(\bar{x}(r_k)) = 0$ .

Um dos autores deste material sugeriu a adição de uma imagem que ilustre geometricamente o significado do teorema acima.

Demonstração

Se (1) acontece, então $f + \frac{1}{r}H$ é coerciva, pois

$\lim_{\|x\| \to \infty} f(x) + \frac{1}{r}H(x) \ge \lim_{\|x\| \to \infty} f(x) = \infty$

A desigualdade é válida pois $H$ é uma função de penalidade, portanto não negativa, e a igualdade se deve à hipotese sobre $f$ . Além de coerciva, tal função é contínua (pois é combinação linear de funções contínuas). Logo, a função possui um ponto de mínimo global, ou seja, existe $\bar{x} \in \mathbb{R}^n$ tal que

$f(\bar{x}) + \frac{1}{r}H(\bar{x}) \le f(x) + \frac{1}{r}H(x)$

, para qualquer $x \in \mathbb{R}^n$ .

Mas $f$ é contínua e coerciva, então também existe $x^* \in \mathbb{R}^n$ tal que

$f(x^*) \le f(x), \forall x \in C$

Por outro lado, se vale (2), então $f + \frac{1}{r}H$ é contínua e C compacto. Analogamente, $f$ é contínua e $C$ compacto, donde tem-se algum $x^* \in C$ tal que

$f(x^*) \le f(x), \forall x \in C$

Em ambos os casos, dada uma sequência $\left\{r_k\right\}$ tal que $0 < r k + 1 < r k$ e $\lim_{k \to \infty} r_k = \infty$ , defina-se $\varphi: \mathbb{R}^n \times \mathbb{R} \mapsto \mathbb{R}$ por $\varphi (x,r) = f(x) + \frac{1}{r}H(x)$ . Logo,

$\begin{array}{lcl} \varphi(\bar{x}(r_k), r_k) & = & f(\bar{x}(r_k)) + \frac{1}{r_k}H(\bar{x}(r_k)) \\ \ & \le & f(\bar{x}(r_{k+1})) + \frac{1}{r_k}H(\bar{x}(r_{k+1}) \\ \ & \le & f(\bar{x}(r_{k+1})) + \frac{1}{r_{k+1}}H(\bar{x}(r_{k+1}) \\ \ & = & \varphi(\bar{x}(r_{k+1}), r_{k+1}) \end{array}$

Sendo que a primeira desigualdade se deve ao fato de $\bar{x}(r_k)$ ser um minimizador, por construção, e a segunda segue por que ${r k}$ é decrescente. Portanto, $\varphi(\bar{x}(r_k), r_k) \le \varphi(\bar{x}(r_{k+1}), r_{k+1}), \forall k$ .

Além disso, tem-se as seguintes desigualdades:

$f(\bar{x}(r_{ k })) + \frac{1}{r_{ k }}H(\bar{x}(r_{ k })) \le f(\bar{x}(r_{k+1})) + \frac{1}{r_{ k }}H(\bar{x}(r_{k+1}))$

$f(\bar{x}(r_{k+1})) + \frac{1}{r_{k+1}}H(\bar{x}(r_{k+1})) \le f(\bar{x}(r_{ k })) + \frac{1}{r_{k+1}}H(\bar{x}(r_{ k }))$

Logo, somando os membros correspondentes, obtem-se:

$\frac{1}{r_k}H(\bar{x}(r_k)) + \frac{1}{r_{k+1}}H(\bar{x}(r_{k+1})) \le \frac{1}{r_k}H(\bar{x}(r_{k+1})) + \frac{1}{r_{k+1}}H(\bar{x}(r_{k}))$

ou seja,

$\left( \frac{1}{r_{k+1}} - \frac{1}{r_{k}}\right) H(\bar{x}(r_{k+1})) \le \left( \frac{1}{r_{k+1}} - \frac{1}{r_{k}}\right) H(\bar{x}(r_{k}))$

Portanto,

$H(\bar{x}(r_{k+1})) \le H(\bar{x}(r_{k})), \forall k$

Por outro lado, $f(\bar{x}(r_k)) \le f(\bar{x}(r_k)) + \frac{1}{r_k}H(\bar{x}(r_k)) \le f(x^*) + \frac{1}{r_k}H(x^*) = f(x^*), \forall k$ , sendo primeira desigualdade válida por $H$ ser não negativa e $r k$ positivo, e a segunda devida à própria definição de $\bar{x}(r_k)$ . Logo, $f(\bar{x}(r_k)) \le f(x^*)$ .

Se a primeira das hipóteses acontece, segue da coercividade e dessa última desigualdade que $\{\bar{x}(r_k)\} \subset L_f(f(x^*))$ . Então $\{\bar{x}(r_k)\}_{i=1}^{\infty}$ é uma sequência limitada.

Se ocorre a segunda, então $H$ é coerciva, mas foi mostrado que $H(\bar{x}(r_{k+1})) \le H(\bar{x}(r_{k}))$ , consequentemente $\{\bar{x}(r_{k+1})\} \subset L_H(H(\bar{x}(r_1)))$ . Sendo $H$ coerciva, conclui-se novamente que $\{\bar{x}(r_k)\}_{i=1}^{\infty}$ é uma sequência limitada.

Portanto, em qualquer caso, $\{\bar{x}(r_k)\}_{i=1}^{\infty}$ possui algum ponto de acumulação.

Seja $\bar{x}$ um ponto de acumulação de $\{\bar{x}(r_k)\}_{i=1}^{\infty}$ . Então existe $\{\bar{x}(r_{k_n})\} \subset \{\bar{x}(r_k)\}$ tal que $\lim_{n \to \infty}\bar{x}(r_{k_n}) = \bar{x}$ . Logicamente, $\lim_{n \to \infty}r_{k_n} = 0$ . Pela continuidade de $f$ e sabendo que $f(\bar{x}(r_k)) \le f(x^*)$ , se deduz que $f(\bar{x}) = \lim_{n \to \infty}f(\bar{x}(r_{k_n})) \le f(x^*)$ . Mas já havia sido verificado que $f(x^*) \le f(x), \forall x \in C$ , então segue a igualdade $f(\bar{x}) = f(x^*)$ .

A sequência $\{\varphi(\bar{x}(r_k), r_k)\}$ é crescente. Seja $\bar{\varphi} = \lim_{n \to \infty}\varphi(\bar{x}(r_k),r_k)$ (por que razão ele existe?). Como $\varphi(\bar{x}(r_k),r_k) = f(\bar{x}(r_k)) + \frac{1}{r_k}H(\bar{x}(r_k))$ , tem-se $\bar{\varphi} = \lim_{n \to \infty}\frac{1}{r_k}H(\bar{x}(r_k)) = \lim_{n \to \infty}\varphi(\bar{x}(r_k),r_k) - \lim_{n \to \infty}f(\bar{x}(r_k)) = \bar{\varphi}-f(\bar{x})$ . Portanto, $\lim_{n \to \infty}H(\bar{x}(r_{k_n})) = 0$ . Logo $\lim_{k \to \infty}H(\bar{x}(r_k))$ , ou seja, $\lim_{r \to 0}H(\bar{x}(r))$ .

Como $H$ é contínua, $\lim_{n \to \infty}H(\bar{x}(r_{k_n})) = H(\bar{x})$ , e este valor é nulo se, e somente se, $\bar{x} \in C$ .

Logo, $f(\bar{x}) \le f(x^*) \le f(\bar{x})$ , donde $f(\bar{x}) = f(x^*)$ . Assim, tem-se $f(\bar{x}) = f(x^*) \le f(x), \forall x \in C$ , ou seja, $\bar{x}$ é solução de (P).

Exercício

Dado o problema (P), considere $m = \inf \left\{ f(x) : g_i(x) \le 0, \forall i \ \text{e}\ h_j = 0, \forall j\right\}$ (isso não quer dizer que o problema tenha solução). suponha-se que $f, g$ e $h$ são funções contínuas e que $C = \left\{x: g_i(x) \le 0, \forall i ; h_j(x) = 0, \forall j\right\}$ seja não vazio, ou seja, que $C$ é factível. Tome $H: \mathbb{R}^n \mapsto \mathbb{R}$ como $H(x) = \sum_{i=1}^{p}[g_i^+(x)]^2 + \sum_{j=1}^{q}[h_j(x)]^2$ , onde $g_i^+$ denota a parte positiva de $g i$ , como de costume. Considere ainda $\varphi: \mathbb{R}^n \times \mathbb{R}^+ \mapsto \mathbb{R}$ dada por $\varphi (x,r) = f(x) + \frac{1}{r}H(x)$ e, para cada $r > 0$ , seja $m(r) = \inf_{x \in \mathbb{R}^n} \varphi(x,r)$ Nessas condições, provar que:

$H$ é uma função de penalidade exterior
$m>-\infty$
$\varphi(x,r) = f(x), \forall x \in C, \forall r>0$
Se $0 < r < s$ então $m (s) < m (r)$
Se $f, g i, h j$ são covexas, então $\varphi$ é convexa.
Se $f, g i, h j$ são diferenciáveis, então $\varphi$ é diferenciável em $x$ , e $\nabla_x\varphi(x,r) = \nabla f(x) + \sum_{i=1}^{p}g_i^+(x)\nabla g_i(x) + \sum_{j=1}^{q}h_j(x)\nabla h_j(x)$
Se $0 < r k + 1 < r k$ e $\lim_{k\to\infty} r_k = 0$ e se ${x k}$ é uma sequência tal que $\varphi(x_k,r_k) = m(r_k)$ e $\lim_{k\to\infty} x_k = \bar{x}$ então $\bar{x}$ é solução de (P).

[editar] Algoritmo de penalidade exterior

Primeiro passo: Escolha ,  $r > 0$  e  $k = 1$ 

Passo iterativo  $k$ : Calcular , solução global de 

Escolha  $r k$  tal que  $0 < r k < r k - 1$

Nota: Neste algoritmo, $H$ é uma função de penalidade exterior.

Exercício

Sejam $f (x, y) = x 2 + y 2$ e $C = \{ (x,y)\in \mathbb{R}^2 : -x \le 0; -y \le 0; x + y - 1 \le 0 \}$ . Considere o problema: $(P) \left\{\begin{matrix} \min f(x,y)\\ (x,y) \in \mathbb{R}^n \end{matrix}\right.$ Utilize o método de penalidade exterior para determinar o ponto de mínimo da função $f$ sobre o conjunto $C$ .

Resolução

Esboço: Pode-se tomar $H(x,y) = \sum_{i=1}^{3} (g_i^+ (x,y))^2$ , onde:

g 1 (x, y) = - x

g 2 (x, y) = - y

g 3 (x, y) = x + y - 1

Tem-se então o problema irrestrito: $(P_r) \left\{\begin{matrix} \min f(x,y) + \frac{1}{r}H(x,y)\\ (x,y) \in \mathbb{R}^2 \end{matrix}\right.$ , onde pode ser aplicado o método de gradientes conjugados.

[editar] Implementação do algoritmo de penalidade exterior em SciLab

Considerando o problema

$(P) \left\{\begin{matrix} min f(x)\\ g_i(x)\le 0 \forall i = 1, \ldots, p\\ h_i(x) = 0 \forall j = 1, \ldots, q \end{matrix}\right.$

com $f$ uma função quadrática, $A$ simétrica positiva definida, $g i, h j$ lineares, e a função de penalidade, $H$ , dada por:

$H(x) = \sum_{i=1}^{p} (g_i^+ (x,y))^2 + \sum_{j=1}^{q} (h_j (x,y))^2$

Pode-se usar o método dos gradientes conjugados para resolver o seguinte problema:

$(P) \left\{\begin{matrix} min f(x) + H(x)\\ x \in \mathbb{R}^n \end{matrix}\right.$

onde $f + H$ terá sua matriz Hessiana definida positiva.

Incluir o código para uma implementação do método em SciLab.

[editar] Método de penalidade interior

Este método também é conhecido como método de barreira. Ele consistem em trabalhar com funções de penalidade tais que $\forall x \in \partial C$ e qualquer que seja a sequência $\{x_n\} \subset C = \{x: g_i(x) < 0\}$ para a qual $x_n \to x$ , se tem que a função de penalidade tende a $+\infty$ .

Um dos autores deste material sugeriu a adição de uma imagem para ilustrar uma sequência de pontos que tende a um ponto da fronteira de um conjunto C, de preferência junto com o gráfico de uma função de penalidade deste novo tipo.

Mas como conseguir esse tipo de função?

[editar] Exemplos

Considere o caso em que $g_i(x) = a_i^\top x - b_i$ . Lembrando que a função logarítmica tem a a propriedade:

$\lim_{x\to 0^+}-\ln(x) = +\infty$

pode-se tomar $H_1(x) = -\sum_{i=1}^{p}\ln(b_i-a_i^\top x)$ , pois

$\lim_{a_i^\top x\to b_i}-\ln(b_i-a_i^\top x) = +\infty$

implica que

$\lim_{x\to \partial C} H_1(x) = +\infty$

Analogamente, tem-se

$\lim_{x\to 0^+} \frac{1}{x} = +\infty$

então, uma outra função com a propriedade desejada é $H_2(x) = \sum_{i=1}^{p}\frac{1}{b_i-a_i^\top x}$ .

O problema a ser resolvido quando se quer aplicar o método de barreira é o seguinte:

$(P) \left\{\begin{matrix} \min f(x)\\ g_i(x) \le 0; i = 1, \ldots, p \end{matrix}\right.$

onde $C = \{ x: g_i(x) \le 0, \forall i\}$ é tal que $C^0 = \{ x: g_i(x) < 0, \forall i\} \not = \emptyset$

Observação: $C 0$ não é necessariamente igual ao interior do conjunto $C$ . Por exemplo:

Um dos autores deste material sugeriu a adição de uma imagem para ilustrar um conjunto C cujo correspondente C0 seja diferente do interior de C.

Definição

Se diz que uma função $B: C^0 \mapsto \mathbb{R}$ é uma função de barreira se ela possui as seguintes propriedades:

$B$ é limitada inferiormente em $C$ .
Para qualquer sequência $\{ x_n\} \subset C^0$ tal que $\lim_{n \to \infty} x_n = x \in \partial C$ vale $\lim_{n \to \infty} B(x_n) = +\infty$
$B$ é contínua

[editar] Algoritmo de barreira

Primeiro passo: Escolha ,  $r > 0$  e  $t 0 > 0$ 

Passo iterativo  $k$ : Calcular , solução global de 

Escolha  $t k + 1$  tal que  $0 < t k + 1 < t k$

Observação: Neste método os termos da sequência ${x n}$ estão sempre em $C 0$ .

[editar] Implementação do algoritmo de barreira em SciLab

Considerando o problema

$\left\{\begin{matrix} min f(x)\\ g_i(x)\le 0 \forall i = 1, \ldots, p\\ \end{matrix}\right.$

pode-se usar o método de barreira no conjunto:

$C = \{ x \in \mathbb{R}^n: g_i(x) \le 0 \}$

Pode-se usar qualquer das funções de penalidade interior apresentadas, por exemplo:

$B(x) = \sum_{i=1}^{p}\frac{1}{g_i(x)}$

ou ainda

$B(x) = \sum_{i=1}^{p}-\ln(-g_i(x))$

Como $C^0 = \{ x \in \mathbb{R}^n: g_i(x) < 0 \}$ , o problema passa a ser:

$\left\{\begin{matrix} min f(x) + B(x)\\ x \in C^0 \end{matrix}\right.$

Observação: Note que é necessário conhecer um ponto inicial $x_0 \in C^0$ , para servir de primeira aproximação, ou ponto de partida para o algoritmo.

Otimização/Métodos de penalidades

Origem: Wikilivros, livros abertos por um mundo aberto.

Índice

[editar] Método de penalidade exterior

[editar] Alguns conceitos da topologia

[editar] De volta ao método

[editar] Algoritmo de penalidade exterior

[editar] Implementação do algoritmo de penalidade exterior em SciLab

[editar] Método de penalidade interior

[editar] Exemplos

[editar] Algoritmo de barreira

[editar] Implementação do algoritmo de barreira em SciLab

Acessos

Ferramentas pessoais

Pesquisa

Navegação

Projecto

Imprimir/exportar

Ferramentas