Estou tentando resolver alguns problemas de otimização não-linear sem restrições na GPU (CUDA).
A função objetivo é uma função não-linear suave e seu gradiente é relativamente barato para calcular analiticamente, portanto, não preciso me preocupar com a aproximação numérica.
Quero resolver esse problema principalmente com operações matemáticas fp32 (por várias razões); portanto, qual método de otimização não-linear é mais robusto contra erros de arredondamento e tem bom desempenho? (por exemplo, gradiente conjugado / quase newton / região de confiança), alguém já tentou o BFGS na GPU com bons resultados?
BTW, o Hessian, se necessário, é relativamente pequeno no meu caso (<64x64 normalmente), mas preciso resolver milhares desses problemas de otimização em pequena escala simultaneamente.
fonte
Respostas:
Eu implementei uma grande variedade de solucionadores não lineares na GPU, incluindo LBFGS, descida do gradiente Barzilai Borwein e gradiente conjugado não linear.
Para isso, o gradiente conjugado não linear de Dai & Yuan tem sido o mais eficiente. Em geral, outra versão do gradiente conjugado não linear pode ser mais eficiente (como CG-DESCENT), mas também pode ser mais difícil de implementar.
Em geral, o LBFGS é uma escolha muito sólida e, a menos que você esteja realmente precisando de memória, é provavelmente o melhor lugar para começar.
O gradiente conjugado e o BFGS requerem pesquisas de linha, que é onde o fp32 se torna um problema. Em vez de usar as condições padrão de Wolfe para a pesquisa de linhas, sugiro usar a condição aproximada de Wolfe sugerida aqui . O artigo está um pouco envolvido, mas o importante é a equação 4.1. Essencialmente, eles explicitamente introduzem a precisão com a qual você pode calcular sua função.
Considerações para a GPU:
Você tem muitos pequenos problemas, o que é um pouco diferente do meu caso de uso de um grande problema. Considere executar 1 problema por bloco de GPU (ou warp, em vez disso) se você puder paralelizar avaliações de função e gradiente para usar todos os threads em um bloco. Dessa forma, não será um problema se problemas diferentes exigirem um número diferente de iterações.
Se isso não for uma opção, eu usaria o solucionador LBFGS. Se sua função for bem-comportada, você pode simplesmente usar um tamanho de etapa 1 (evitando a pesquisa de linha) e apenas executar todos os problemas para um número fixo de iterações.
fonte
Sugiro que você use o Levenberg Marquardt (uma variante da região de confiança), pois é usado em muitas aplicações práticas e demonstrou um desempenho muito bom de velocidade versus precisão. Além disso, para a GPU, existem algumas bibliotecas (por exemplo, cuLM https://github.com/zitmen/cuLM ), que você pode experimentar. Se eles não fizerem o trabalho, há muitos recursos para você implementar. Implementar o LM não é nada difícil. Você deve cuidar apenas de minimizar a comunicação da GPU. Para ter uma breve ideia:
http://on-demand.gputechconf.com/gtc/2012/presentations/S0231-Levenberg-Marquardt-Using-Block-Sparse-Matrices-on-CUDA.pdf
fonte
Talvez um procedimento de recozimento simulado possa lidar melhor com erros de arredondamento (e é facilmente paralelizado).
Você começa com uma grade bruta da área de pesquisa e um parâmetro inicial de "temperatura"
Em cada etapa, você calcula pontos de solução possíveis (também é possível aceitar pontos sem solução, com alguma probabilidade inversamente análoga à temperatura)
Em seguida, retenha apenas as soluções nessa etapa e aumente a temperatura, proporcionando uma grade mais refinada para a próxima iteração
Faça isso até a temperatura <um determinado limite / limiar de precisão
fonte