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

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:

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

$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

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:

$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

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.