Saltar para o conteúdo

Otimização/Métodos de penalidades

Origem: Wikilivros, livros abertos por um mundo aberto.
Wikipedia
Wikipedia
A Wikipédia tem mais sobre este assunto:
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:

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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. Se então
  3. Se são covexas, então é convexa.
  4. Se são diferenciáveis, então é diferenciável em , e
  5. Se e e se é uma sequência tal que e então é solução de (P).

Algoritmo de penalidade exterior

[editar | editar código-fonte]
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 | 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.

Método de penalidade interior

[editar | editar código-fonte]

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.
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 | editar código-fonte]
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.