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:

Gráfico de uma função de penalidade

$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)\}$

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)\leq 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)\leq 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)\leq 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)\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$

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)\leq \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)\leq K\Rightarrow \|x\|\leq M$ (sua contrapositiva). Pela definição de conjunto de nível, isso equivale à $x\in L_{\theta }(K)\Rightarrow \|x\|\leq 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}\leq 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}})\leq 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}})\leq 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\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:

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)\geq \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}})\leq 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^{*})\leq 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^{*})\leq 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}))\\\ &\leq &f({\bar {x}}(r_{k+1}))+{\frac {1}{r_{k}}}H({\bar {x}}(r_{k+1})\\\ &\leq &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})\leq \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}))\leq 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}))\leq 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}))\leq {\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}))\leq \left({\frac {1}{r_{k+1}}}-{\frac {1}{r_{k}}}\right)H({\bar {x}}(r_{k}))$ Portanto, $H({\bar {x}}(r_{k+1}))\leq H({\bar {x}}(r_{k})),\forall k$ Por outro lado, $f({\bar {x}}(r_{k}))\leq f({\bar {x}}(r_{k}))+{\frac {1}{r_{k}}}H({\bar {x}}(r_{k}))\leq 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}))\leq 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}))\leq 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}))\leq f(x^{*})$, se deduz que $f({\bar {x}})=\lim _{n\to \infty }f({\bar {x}}(r_{k_{n}}))\leq f(x^{*})$. Mas já havia sido verificado que $f(x^{*})\leq 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}})\leq f(x^{*})\leq f({\bar {x}})$, donde $f({\bar {x}})=f(x^{*})$. Assim, tem-se $f({\bar {x}})=f(x^{*})\leq 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)\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:

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

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

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)\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:

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