Estoy tratando de resolver algunos problemas de optimización no lineal sin restricciones en la GPU (CUDA).
La función objetivo es una función no lineal suave, y su gradiente es relativamente barato de calcular analíticamente, por lo que no necesito molestarme con la aproximación numérica.
Quiero resolver este problema principalmente con operaciones matemáticas de fp32 (por varias razones), entonces, ¿qué método de optimización no lineal es más robusto contra errores de redondeo y tiene un buen rendimiento? (p. ej., gradiente conjugado / cuasi newton / región de confianza), ¿alguien ha probado BFGS en GPU con buenos resultados?
Por cierto, el Hessian, si es necesario, es relativamente pequeño en mi caso (<64x64 típicamente), pero necesito resolver miles de estos problemas de optimización a pequeña escala al mismo tiempo.
fuente
Respuestas:
He implementado una gran variedad de solucionadores no lineales en la GPU, incluidos LBFGS, descenso de gradiente Barzilai Borwein y gradiente conjugado no lineal.
Para esto, el gradiente conjugado no lineal de Dai y Yuan ha sido el más eficiente. En general, otra versión del gradiente conjugado no lineal puede ser más eficiente (como CG-DESCENT), pero también puede ser más difícil de implementar.
LBFGS es, en general, una opción muy sólida, y a menos que realmente tenga problemas de memoria, probablemente sea el mejor lugar para comenzar.
Sin embargo, tanto el gradiente conjugado como BFGS requieren búsquedas de líneas, que es donde el fp32 se convierte en un problema. En lugar de usar las condiciones estándar de Wolfe para la búsqueda de línea, sugeriría usar la condición aproximada de Wolfe sugerida aquí . El artículo es un poco complicado, pero lo importante es la ecuación 4.1. Esencialmente, introducen explícitamente la precisión con la que puede calcular su función.
Consideraciones para la GPU:
Tiene muchos problemas pequeños, que es ligeramente diferente de mi caso de uso de un gran problema. Considere ejecutar 1 problema por bloque de GPU (o warp, más bien) si puede paralelizar evaluaciones de función y gradiente para usar todos los hilos en un bloque. De esa manera no es un problema si diferentes problemas requieren un número diferente de iteraciones.
Si esto no es una opción, iría con el solucionador LBFGS. Si su función se comporta bien, puede salirse con la suya simplemente usando un tamaño de paso de 1 (evitando la búsqueda de línea) y simplemente ejecutando todos los problemas para un número fijo de iteraciones.
fuente
Le sugiero que use Levenberg Marquardt (una variante de región de confianza), ya que se usa en muchas aplicaciones prácticas y demostró un muy buen rendimiento de velocidad frente a precisión. Además, para GPU hay algunas bibliotecas (por ejemplo, cuLM https://github.com/zitmen/cuLM ), que puede probar. Si no hacen el trabajo, hay toneladas de recursos para implementar. Implementar LM no es difícil en absoluto. Solo debe tener cuidado de minimizar la comunicación de GPU. Para tener una breve idea:
http://on-demand.gputechconf.com/gtc/2012/presentations/S0231-Levenberg-Marquardt-Using-Block-Sparse-Matrices-on-CUDA.pdf
fuente
Quizás un procedimiento de recocido simulado pueda manejar mejor los errores de redondeo (y se paraleliza fácilmente).
Usted comienza con una grilla cruda del área de búsqueda y un parámetro inicial de "temperatura"
En cada paso, calcula los posibles puntos de solución (también se pueden aceptar puntos sin solución, con alguna probabilidad inversamente análoga a la temperatura)
Luego, conserve solo las soluciones en ese paso y aumente la temperatura, lo que proporciona una cuadrícula más fina para la próxima iteración
Haga esto hasta que la temperatura <un límite / umbral de precisión dado
fuente