Método de penalidade

Os métodos de penalidade são uma certa classe de algoritmos para resolver problemas de otimização restritos .

Um método de penalidade substitui um problema de otimização restrito por uma série de problemas irrestritos cujas soluções convergem idealmente para a solução do problema restrito original. Os problemas irrestritos são formados pela adição de um termo, denominado função de penalidade , à função objetivo que consiste em um parâmetro de penalidade multiplicado por uma medida de violação das restrições. A medida de violação é diferente de zero quando as restrições são violadas e é zero na região onde as restrições não são violadas.

Descrição

Digamos que estamos resolvendo o seguinte problema restrito:

sujeito a

Este problema pode ser resolvido como uma série de problemas de minimização irrestritos

onde

Nas equações acima, é a função de penalidade externa enquanto é o coeficiente de penalidade . Quando o coeficiente de penalidade é 0, f p = f . Em cada iteração do método, aumentamos o coeficiente de penalidade (por exemplo, por um fator de 10), resolvemos o problema irrestrito e usamos a solução como estimativa inicial para a próxima iteração. As soluções dos sucessivos problemas irrestritos convergirão assintoticamente para a solução do problema original com restrições.

Convergência

Consideramos primeiro o conjunto de otimizadores globais do problema original, X*. [1] : Thm.9.2.1  Suponha que o objetivo f tenha conjuntos de níveis limitados e que o problema original seja viável. Então:

  • Para cada coeficiente de penalidade p , o conjunto de otimizadores globais do problema penalizado, X p *, não é vazio.
  • Para cada ε>0, existe um coeficiente de penalidade p tal que o conjunto X p * está contido em uma vizinhança ε do conjunto X*.

Este teorema é útil principalmente quando f p é convexo, pois neste caso podemos encontrar os otimizadores globais de f p .

Um segundo teorema considera otimizadores locais. [1] : Thm.9.2.2  Seja x* um otimizador local não degenerado do problema original ("não degenerado" significa que os gradientes das restrições ativas são linearmente independentes e a condição de otimalidade suficiente de segunda ordem é satisfeita). Então, existe uma vizinhança V* de x*, e algum p 0 >0, tal que para todo p > p 0 , o objetivo penalizado f p tem exatamente um ponto crítico em V* (denotado por x*(p)) , e x*( p ) se aproxima de x* quando p →∞. Além disso, o valor objetivo f (x*( p )) aumenta fracamente com p .

Aplicações práticas

Algoritmos de otimização de compressão de imagem podem fazer uso de funções de penalidade para selecionar a melhor forma de compactar zonas de cor em valores representativos únicos. [2] [3]

A vantagem do método de penalidade é que, uma vez que tenhamos um objetivo penalizado e sem restrições, podemos utilizar qualquer método de otimização sem restrições para resolvê-lo. A desvantagem é que, à medida que o coeficiente de penalidade p cresce, o problema irrestrito torna -se mal condicionado - os coeficientes são muito grandes, e isso pode causar erros numéricos e convergência lenta da minimização irrestrita. [1] : Sub.9.2 

Veja também

Os métodos de barreira constituem uma classe alternativa de algoritmos para otimização restrita. Esses métodos também adicionam um termo semelhante a uma penalidade à função objetivo, mas neste caso as iterações são forçadas a permanecer interiores ao domínio viável e a barreira existe para inclinar as iterações a permanecerem longe do limite da região viável. São praticamente mais eficientes que os métodos de penalidade.

Os métodos Lagrangeanos Aumentados são métodos de penalidade alternativos, que permitem obter soluções de alta precisão sem levar o coeficiente de penalidade ao infinito. Isso torna os problemas penalizados irrestritos mais fáceis de resolver.

Outros algoritmos de programação não linear:

Referências

  1. ^ abc Nemirovsky e Ben-Tal (2023). "Otimização III: Otimização Convexa" (PDF) .
  2. ^ Galar, M.; Júrio, A.; López-Molina, C.; Paternain, D.; Sanz, J.; Bustince, H. (2013). "Funções de agregação para combinar canais de cores RGB em correspondência estéreo". Ótica Expressa . 21 (1): 1247–1257. doi :10.1364/oe.21.001247. hdl : 2454/21074 . PMID23389018  .
  3. ^ “Pesquisadores restauram imagem usando versão contendo entre 1 e 10 por cento de informação” . Phys.org (Omicron Technology Limited) . Recuperado em 26 de outubro de 2013 .

Smith, Alice E .; Coit David W. Funções de penalidade Manual de Computação Evolucionária, Seção C 5.2. Imprensa da Universidade de Oxford e Publicação do Instituto de Física, 1996.

Coello, AC[1]: Técnicas teóricas e numéricas de tratamento de restrições usadas com algoritmos evolutivos: um levantamento do estado da arte. Computação. Métodos Apl. Mecânico. Eng. 191(11-12), 1245-1287

Courant, R. Métodos variacionais para a solução de problemas de equilíbrio e vibrações. Touro. Amer. Matemática. Soc., 49, 1–23, 1943.

Wotao, Y. Algoritmos de otimização para otimização restrita. Departamento de Matemática, UCLA, 2015.

Obtido em "https://en.wikipedia.org/w/index.php?title=Penalty_method&oldid=1189988861"