# 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}minf(x)\\g_{i}(x)\leq 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)\leq 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}minf(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}minf(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\leq 0\\\infty ,&{\mbox{se }}t>0\end{cases}}$
Tem-se ainda o problema (PP), dado por:
$(PP)\left\{{\begin{matrix}minf(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:
    $H:\mathbb {R} \mapsto \mathbb {R}$
    $H(t)={\begin{cases}0,&{\mbox{se }}t\leq 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)\}$

### 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.

### 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}$.
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)\geq 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)\leq 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$
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)\leq \lambda \}$ é limitado para todo $\lambda \in \mathbb {R}$.

### 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}$.

### 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}})\leq g(x),\forall x\in \mathbb {R} ^{n}$.

### 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\geq 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)\leq 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:
* $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$.

#### Exercício

Dado o problema (P), considere $m=\inf \left\{f(x):g_{i}(x)\leq 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)\leq 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).

### Algoritmo de penalidade exterior

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\leq 0;-y\leq 0;x+y-1\leq 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$.

### Implementação do algoritmo de penalidade exterior em SciLab

Considerando o problema
    $(P)\left\{{\begin{matrix}minf(x)\\g_{i}(x)\leq 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}minf(x)+H(x)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$
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 $\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$.
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)\leq 0;i=1,\ldots ,p\end{matrix}}\right.$
onde $C=\{x:g_{i}(x)\leq 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:

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

### Algoritmo de barreira

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}minf(x)\\g_{i}(x)\leq 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)\leq 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}minf(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.