Testando métodos de otimização numérica: Rosenbrock x funções de teste reais

15

Parece haver dois tipos principais de função de teste para otimizadores sem derivação:

  • one-liners como a função Rosenbrock ff., com pontos de partida
  • conjuntos de pontos de dados reais, com um interpolador

É possível comparar, digamos, a 10d Rosenbrock com algum problema 10d real?
Pode-se comparar de várias maneiras: descrever a estrutura dos mínimos locais
ou executar os otimizadores ABC em Rosenbrock e alguns problemas reais;
mas ambos parecem difíceis.

(Talvez teóricos e experimentadores sejam apenas duas culturas bem diferentes, então estou pedindo uma quimera?)

Veja também:


(Adicionado em setembro de 2014):
O gráfico abaixo compara 3 algoritmos DFO em 14 funções de teste em 8d a partir de 10 pontos de início aleatórios: BOBYQA PRAXIS SBPLX de NLOpt 14 funções de teste N-dimensionais, Python sob o gist.github deste Matlab por A Hedar 10 pontos de início aleatórios uniformes na caixa delimitadora de cada função.
×
×

Em Ackley, por exemplo, a linha superior mostra que SBPLX é melhor e PRAXIS terrível; em Schwefel, o painel inferior direito mostra o SBPLX encontrando um mínimo no quinto ponto inicial aleatório.

No geral, BOBYQA é melhor em 1, PRAXIS em 5 e SBPLX (~ Nelder-Mead com reinicializações) em 7 de 13 funções de teste, com Powersum um lançamento. YMMV! Em particular, Johnson diz: "Eu aconselho você a não usar valor de função (ftol) ou tolerâncias de parâmetro (xtol) na otimização global".

Conclusão: não coloque todo o seu dinheiro em um cavalo ou em uma função de teste.

insira a descrição da imagem aqui

denis
fonte

Respostas:

13

Funções simples como a de Rosenbrock são usadas para depurar e pré-testar algoritmos recém-escritos: são rápidos de implementar e executar, e é improvável que um método que não consiga resolver bem os problemas padrão funcione bem nos problemas da vida real.

Para uma comparação completa recente de métodos sem derivativos para funções caras, consulte Otimização sem derivadas: uma revisão de algoritmos e comparação de implementações de software . LM Rios, NV Sahinidis - doi 10.1007 / s10898-012-9951-y Journal of Global Optimization, 2012. (Veja também a página da Web em anexo: http://archimedes.cheme.cmu.edu/?q=dfocomp )

Arnold Neumaier
fonte
Prof. Neumaier, você poderia apontar alguns problemas reais, evidências, pois "é improvável que um método que não consiga resolver bem os problemas padrão funcione bem em problemas da vida real"? Eu percebo que isso não é fácil. (Eu estaria interessado nos seus comentários sobre Hooker.) Além disso, uma rápida olhada nos modelos c do seu link mostra que princetonlibgloballib requer AMPL e source_convexmodels * .c todos têm um ";" após fscanf () - trivial mas
denis
@ Denis: Problemas como o Rosenbrock decorrem dos primeiros dias da otimização automatizada, onde as pessoas isolavam as dificuldades típicas em exemplos representativos simples que podem ser estudados sem as complexidades numéricas dos problemas da vida real. Portanto, eles não são realmente artificiais, mas modelos simplificados de dificuldades reais. Por exemplo, Rosenbrock ilustra o efeito combinado de forte não linearidade e condições leves.
Arnold Neumaier 11/08/2012
O site da AMPL ampl.com oferece uma versão gratuita para estudantes da AMPL.
Arnold Neumaier 11/08/2012
7

A vantagem de casos de teste sintéticos, como a função Rosenbrock, é que existe literatura existente para comparar e existe um senso na comunidade de como os métodos se comportam nesses casos. Se todos usassem seu próprio caso de teste, seria muito mais difícil chegar a um consenso sobre quais métodos funcionam e quais não.

Wolfgang Bangerth
fonte
1

(Espero que não haja nenhuma objeção em relação ao final desta discussão. Sou novo aqui, por favor, deixe-me saber se transgredi!)

As funções de teste para algoritmos evolutivos agora são muito mais complicadas do que eram há 2 ou 3 anos, como pode ser visto pelas suítes usadas em competições em conferências como o (muito recente) Congresso de 2015 em Computação Evolucionária. Vejo:

http://www.cec2015.org/

Esses conjuntos de testes agora incluem funções com várias interações não lineares entre variáveis. O número de variáveis ​​pode ser tão grande quanto 1000, e eu acho que isso pode aumentar no futuro próximo.

Outra inovação muito recente é uma "Competição de otimização de caixa preta". Veja: http://bbcomp.ini.rub.de/

Um algoritmo pode consultar o valor f (x) para obter um ponto x, mas não obtém informações de gradiente e, em particular, não pode fazer nenhuma suposição sobre a forma analítica da função objetivo.

Em certo sentido, isso pode estar mais próximo do que você chamou de "problema real", mas em um ambiente organizado e objetivo.

Lisístrata
fonte
1) "sem objeção": pelo contrário, seus bons links são bem-vindos! 2) alguma boa parcela lá? Os métodos e os problemas são fractalizadores, por isso está ficando cada vez mais difícil para qualquer um encontrar um problema como o deles. Em particular, você conheceria métodos para previsão de séries temporais ?
Denis10 /
As funções de objetivo da competição CEC 2015 sobre otimização dinâmica de múltiplos objetivos podem ser vistas em: sites.google.com/site/cec2015dmoocomp/competition-process/… Para outras competições, acesse cec2015.org e clique em competições, depois clique em em competições aceitas. Cada um tem suas próprias funções. Trabalhos em alguns deles têm enredos adoráveis ​​(para os casos 2D). Competições conferência Gecco podem ser encontradas em: sigevo.org/gecco-2015/competitions.html#bbc Os resultados estarão disponíveis após 15 de julho
Lisístrata
0

Você pode ter o melhor dos dois mundos. O NIST tem um conjunto de problemas para minimizadores, como ajustar esse polinômio de 10º grau , com resultados esperados e incertezas. Evidentemente, provar que esses valores são a melhor solução real ou a existência e propriedades de outros mínimos locais é mais difícil do que em uma expressão matemática controlada.

Davidmh
fonte
Bem, os problemas do NIST são pequenos (2 3 1 1 11 7 6 6 6 6 6 parâmetros). Existem conjuntos de testes que são "reais" e reprodutíveis para qualquer canto de "real"? Cf. um Pedido de simulação baseada em Problemas de Otimização
denis