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;
Wikipedia
Wikipedia
A Wikipédia tem mais sobre este assunto:
Métodos de penalidades

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 :

Método de penalidade exterior

editar

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
 
 
Definição

Dada uma função  , definida em um conjunto arbitrário  , define-se a parte positiva de  , como:

 


  Um dos autores deste material sugeriu a adição de uma imagem para comparar uma função   e sua correspondente  .
Exercício

Verifique que para cada   tem-se, para cada  , a igualdade  , onde   é a parte positiva de   e   é a função definida no exemplo anterior.


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  .

Exercício

Verifique que para cada   tem-se, para cada  , a igualdade  .


  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:

  •  
  •  
  •   é contínua

Nota: Lembre-se que   é o conjunto viável do problema (P).

Em particular, as funções   são funções de penalidade exterior.

Definição

Seja  . A função   é dita coerciva se  


  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   é uma função coerciva se, e somente se,   é limitado para todo  .

Resolução
Pela definição de limite, a afirmação
 

é equivalente a dizer que

  tal que   tem-se  .

Esta última implicação, é equivalente à

  (sua contrapositiva).

Pela definição de conjunto de nível, isso equivale à  . A existência de um número   com tal propriedade significa que   é 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   definida por   é uma função de penalidade exterior, onde conforme anteriormente,   é a parte positiva de  .


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.

Exercício

Verifique que se   é uma função contínua coerciva, então existe   tal que  .


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.

Alguns conceitos da topologia

editar

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  , uma coleção   de subconjuntos de   é chamada de topologia se:

  •  
  •  
  •  

Exemplos
  • Topologia euclidiana:
 
 

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:
 
 

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

Definição

 

De volta ao método

editar

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:
  1.   é coerciva.
  2.   é limitado e   é coerciva.
Se, para cada  , for escolhido  ,então:
  1.   possui algum ponto de acumulação;
  2. Todo ponto de acumulação de   é solução do problema (P);
  3.  .


  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:

  1.   é uma função de penalidade exterior
  2.  
  3.  
  4. Se   então  
  5. Se   são covexas, então   é convexa.
  6. Se   são diferenciáveis, então   é diferenciável em  , e  
  7. Se   e   e se   é uma sequência tal que   e   então   é solução de (P).

Algoritmo de penalidade exterior

editar
Primeiro passo: Escolha  ,   e  

Passo iterativo  : Calcular  , solução global de 
 
Escolha   tal que  

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

Exercício

Sejam   e  . Considere o problema:   Utilize o método de penalidade exterior para determinar o ponto de mínimo da função   sobre o conjunto  .

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

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.

Método de penalidade interior

editar

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?

Exemplos

editar

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.
Definição

Se diz que uma função   é uma função de barreira se ela possui as seguintes propriedades:

  1.   é limitada inferiormente em  .
  2. Para qualquer sequência   tal que   vale  
  3.   é contínua

Algoritmo de barreira

editar
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

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.