Otimização/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_j(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_j(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 $\chi_{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 $\phi$ 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))$

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) = max \{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) = max \{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_j(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 $\theta$ é 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 Wikcionário, 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 $\theta$ é 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_\theta(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(\lambda)$ é 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(\lambda)$, 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) > \lambda$ (pela definição do conjunto $L_g(\lambda)$).

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

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.

Outro exemplo muito comum é o seguinte:

• Topologia euclideana estendida:

$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$

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_j(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:

1. $f$ é coerciva.
2. $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:

1. $\left\{ \bar{x}(r_k) \right\}$ possui algum ponto de acumulação;
2. Todo ponto de acumulação de $\left\{ \bar{x}(r_k) \right\}$ é solução do problema (P);
3. $\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:

1. $H$ é uma função de penalidade exterior
2. $m>-\infty$
3. $\varphi(x,r) = f(x), \forall x \in C, \forall r>0$
4. Se $0 < r < s$ então $m(s) < m(r)$
5. Se $f, g_i, h_j$ são covexas, então $\varphi$ é convexa.
6. 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)$
7. 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).

Algoritmo de penalidade exterior

Primeiro passo: Escolha $x_0 \in \mathbb{R}^n$, $r>0$ e $k=1$

Passo iterativo $k$: Calcular $x_k = \bar{x} (r_k)$, solução global de 
$(P) \left\{\begin{matrix}
\min \varphi(x,r_k) & = & f(x) + \frac{1}{2r}H(x)\\
x \in \mathbb{R}^n &   &
\end{matrix}\right.$
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.

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_j(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.

Método de penalidade interior

Este método também é conhecido como método de barreira. Ele consiste 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?

Exemplos

Considere o caso em que $g_i(x) = a_i^\top x - b_i$. Lembrando que a função logarítmica tem 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:

1. $B$ é limitada inferiormente em $C$.
2. 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$
3. $B$ é contínua

Algoritmo de barreira

Primeiro passo: Escolha $x_0 \in C^0$, $r>0$ e $t_0>0$

Passo iterativo $k$: Calcular $x_{k+1} = \bar{x} (t_k)$, solução global de 
$(P) \left\{\begin{matrix}
\min f(x) + t_k B(x)\\
x \in C^0
\end{matrix}\right.$
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$.

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.