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)\{\begin{array}{c}minf(x)\\ g_i(x)\le 0\mathrm{\forall }i=1,\dots ,p\\ h_j(x)=0\mathrm{\forall }j=1,\dots ,q\end{array}$

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

$(P)\{\begin{array}{c}minf(x)\\ x\in C\end{array}$

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

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)\{\begin{array}{c}minf(x)+I_C(x)\\ x\in {ℝ}^n\end{array}$

Considerando $i_C:ℝ\mapsto ℝ\cup \{\mathrm{\infty }\}$ definida por:

$i_C(t)=\{\begin{array}{cc}0,& \text{se }t\le 0\\ \mathrm{\infty },& \text{se }t>0\end{array}$

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

$(PP)\{\begin{array}{c}minf(x)+\sum _{i=1}^{p}i(g_i(x))+\sum _{j=1}^{p}i(h_j(x))\\ x\in {ℝ}^n\end{array}$

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 $\varphi$ definida a seguir é descontínua em cada ponto $x\in \partial C$:

$\varphi :{ℝ}^n\mapsto ℝ\cup \{\mathrm{\infty }\}$

$\varphi (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:ℝ\mapsto ℝ$

$H(t)=\{\begin{array}{cc}0,& \text{se }t\le 0\\ t^2,& \text{se }t>0\end{array}$

A idéia de aplicar penalizações aos pontos que não pertencem ao conjunto viável é formalizada na seguinte definição: Predefinição:Definição Nota: Lembre-se que $C=\{x\in {ℝ}^n:g_i(x)\le 0,\mathrm{\forall }i=1,\dots ,p;h_j(x)=0,\mathrm{\forall }j=1,\dots ,q\}$ é o conjunto viável do problema (P).

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

Nota: Conforme o Wikcionário, o termo Predefinição:Wikt 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.

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.

Exemplos

• Topologia euclidiana:

$X=R$

$\mathrm{\Gamma }={\mathrm{\Gamma }}_1=\{\mathrm{\varnothing }\}\cup \{X\}\cup \{A\subset ℝ:\mathrm{\forall }x\in A,\mathrm{\exists }{ϵ}_x>0,(x-{ϵ}_x,x+{ϵ}_x)\subset A\}$

Em outras palavras, a topologia euclideana é a coleção de todos os conjuntos abertos contidos em $ℝ$. 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 \{\mathrm{\infty }\}$

$\mathrm{\Gamma }={\mathrm{\Gamma }}_1\cup \{A\subset ℝ\cup \{\mathrm{\infty }\}:\mathrm{\exists }a\in ℝ,A=]a,\mathrm{\infty }]\}$

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

De volta ao método

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

Algoritmo de penalidade exterior

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

Passo iterativo $k$: Calcular $x_k=\overline{x}(r_k)$, solução global de 
$(P)\{\begin{array}{ccc}\min \phi (x,r_k)& =& f(x)+\frac{1}{2r}H(x)\\ x\in {ℝ}^n& & \end{array}$
Escolha $r_k$ tal que $0<r_k<r_{k-1}$

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

Implementação do algoritmo de penalidade exterior em SciLab

Considerando o problema

$(P)\{\begin{array}{c}minf(x)\\ g_i(x)\le 0\mathrm{\forall }i=1,\dots ,p\\ h_j(x)=0\mathrm{\forall }j=1,\dots ,q\end{array}$

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)\{\begin{array}{c}minf(x)+H(x)\\ x\in {ℝ}^n\end{array}$

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

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 $\mathrm{\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 $+\mathrm{\infty }$.

Mas como conseguir esse tipo de função?

Exemplos

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

$\underset{x\to 0^{+}}{\lim }-\ln (x)=+\mathrm{\infty }$

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

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

implica que

$\underset{x\to \partial C}{\lim }{H}_1(x)=+\mathrm{\infty }$

Analogamente, tem-se

$\underset{x\to 0^{+}}{\lim }\frac{1}{x}=+\mathrm{\infty }$

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

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

$(P)\{\begin{array}{c}\min f(x)\\ g_i(x)\le 0;i=1,\dots ,p\end{array}$

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

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

Algoritmo de barreira

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

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

$\{\begin{array}{c}minf(x)\\ g_i(x)\le 0\mathrm{\forall }i=1,\dots ,p\end{array}$

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

$C=\{x\in {ℝ}^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 {ℝ}^n:g_i(x)<0\}$, o problema passa a ser:

$\{\begin{array}{c}minf(x)+B(x)\\ x\in C^0\end{array}$

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.