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:
Adicionalmente, se for considerado o conjunto de pontos
, o problema (P) se escreve ainda como
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
, define-se a função indicadora
por:

Notas: A função indicadora
é às vezes denotada por
.
Para transformar um conjunto (P) em um problema sem restrições, pode-se proceder da seguinte maneira: Considerar o problema (PD), dado por:
Considerando
definida por:

Tem-se ainda o problema (PP), dado por:
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
definida a seguir é descontínua em cada ponto
:


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


|
Um dos autores deste material sugeriu a adição de uma imagem para comparar uma função e sua correspondente .
|
Resolução
|
De fato, dada qualquer função , segue da própria definição de que

Mas

implica que

Portanto, . Como pode ser tomada arbitrariamente, tem-se em particular que .
|
|
Um dos autores deste material sugeriu conferir o enunciado do exercício anterior. A afirmação parece ser falsa nos casos em que .
|
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
. A função
é chamada de função de penalidade exterior se possui as seguintes propriedades:
Nota: Lembre-se que
é o conjunto viável do problema (P).
Em particular, as funções
são funções de penalidade exterior.
|
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.
|
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.
|
Resolução
|
Primeiramente, é 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 se, e somente se, para cada índice e cada índice vale e . Como , tem-se
Finalmente, como a soma e o produto de funções contínuas resulta em uma função contínua, segue que é contínua, pois são contínuas.
|
Resolução
|
Considere um ponto arbitrário . Tome . Nestas condições, é 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 possui algum ponto de mínimo no conjunto , ou seja, existe tal que .
Ne verdade, tal ponto é também um minimizador global da função , pois se então (pela definição do conjunto ).
|
|
Um dos autores deste material sugeriu a adição de uma imagem ilustrando a existência de minimizadores globais para funções coercivas.
|
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


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:

![{\displaystyle \Gamma =\Gamma _{1}\cup \left\{A\subset \mathbb {R} \cup \{\infty \}:\exists a\in \mathbb {R} ,A=\left]a,\infty \right]\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1714b9f65c53fef59fd69fcaa4fdb0428af11dd2)
Em geral, a noção de limite seria caracterizada topologicamente da seguinte forma:
- Definição

Uma vez apresentados os conceitos iniciais, pode-se provar o seguinte teorema:
- Teorema
Considere:
uma função de penalidade exterior;
uma função contínua;
um conjunto fechado;
uma sequência de termos positivos tal que
.
Suponha que é válida uma das seguintes propriedades:
é coerciva.
é limitado e
é coerciva.
Se, para cada

, for escolhido

,então:
possui algum ponto de acumulação;
- Todo ponto de acumulação de
é solução do problema (P);
.
|
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 é coerciva, pois

A desigualdade é válida pois é uma função de penalidade, portanto não negativa, e a igualdade se deve à hipotese sobre . 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 tal que

, para qualquer .
Mas é contínua e coerciva, então também existe tal que

Por outro lado, se vale (2), então é contínua e C compacto. Analogamente, é contínua e compacto, donde tem-se algum tal que

Em ambos os casos, dada uma sequência tal que e , defina-se por . Logo,

Sendo que a primeira desigualdade se deve ao fato de ser um minimizador, por construção, e a segunda segue por que é decrescente. Portanto, .
Além disso, tem-se as seguintes desigualdades:


Logo, somando os membros correspondentes, obtem-se:

ou seja,

Portanto,

Por outro lado, , sendo primeira desigualdade válida por ser não negativa e positivo, e a segunda devida à própria definição de . Logo, .
Se a primeira das hipóteses acontece, segue da coercividade e dessa última desigualdade que . Então é uma sequência limitada.
Se ocorre a segunda, então é coerciva, mas foi mostrado que , consequentemente . Sendo coerciva, conclui-se novamente que é uma sequência limitada.
Portanto, em qualquer caso, possui algum ponto de acumulação.
Seja um ponto de acumulação de . Então existe tal que . Logicamente, . Pela continuidade de e sabendo que , se deduz que . Mas já havia sido verificado que , então segue a igualdade .
A sequência é crescente. Seja (por que razão ele existe?). Como , tem-se . Portanto, . Logo , ou seja, .
Como é contínua, , e este valor é nulo se, e somente se, .
Logo, , donde . Assim, tem-se , ou seja, é solução de (P).
|
- Exercício
Dado o problema (P), considere
(isso não quer dizer que o problema tenha solução). suponha-se que
e
são funções contínuas e que
seja não vazio, ou seja, que
é factível. Tome
como
, onde
denota a parte positiva de
, como de costume. Considere ainda
dada por
e, para cada
, seja
Nessas condições, provar que:
é uma função de penalidade exterior


- Se
então 
- Se
são covexas, então
é convexa.
- Se
são diferenciáveis, então
é diferenciável em
, e 
- Se
e
e se
é uma sequência tal que
e
então
é solução de (P).
Primeiro passo: Escolha
,
e
Passo iterativo
: Calcular
, solução global de
Escolha
tal que
Nota: Neste algoritmo,
é uma função de penalidade exterior.
Resolução
|
Esboço: Pode-se tomar , onde:



Tem-se então o problema irrestrito:
,
onde pode ser aplicado o método de gradientes conjugados.
|
Implementação do algoritmo de penalidade exterior em SciLab[editar | editar código-fonte]
Considerando o problema

com
uma função quadrática,
simétrica positiva definida,
lineares, e a função de penalidade,
, dada por:

Pode-se usar o método dos gradientes conjugados para resolver o seguinte problema:

onde
terá sua matriz Hessiana definida positiva.
|
Incluir o código para uma implementação do método em SciLab.
|
Este método também é conhecido como método de barreira. Ele consiste em trabalhar com funções de penalidade tais que
e qualquer que seja a sequência
para a qual
, se tem que a função de penalidade tende a
.
|
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?
Considere o caso em que
.
Lembrando que a função logarítmica tem a propriedade:

pode-se tomar
, pois

implica que

Analogamente, tem-se

então, uma outra função com a propriedade desejada é
.
O problema a ser resolvido quando se quer aplicar o método de barreira é o seguinte:

onde
é tal que
Observação:
não é necessariamente igual ao interior do conjunto
. 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.
|
Primeiro passo: Escolha
,
e
Passo iterativo
: Calcular
, solução global de
Escolha
tal que
Observação: Neste método os termos da sequência
estão sempre em
.
Implementação do algoritmo de barreira em SciLab[editar | editar código-fonte]
Considerando o problema

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

Pode-se usar qualquer das funções de penalidade interior apresentadas, por exemplo:

ou ainda

Como
, o problema passa a ser:

Observação: Note que é necessário conhecer um ponto inicial
, para servir de primeira aproximação, ou ponto de partida para o algoritmo.