Resolver problemas de optimización no lineal sin restricciones en la GPU

18

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.

usuario0002128
fuente
44
Dado el pequeño tamaño de sus problemas, no creo que la elección específica del algoritmo (por ejemplo, BFGS) sea su desafío más importante. En cambio, minimizará los gastos generales de comunicación de la GPU <-> CPU. Probablemente, la mejor manera de hacerlo será resolver muchas instancias de sus problemas en paralelo en la GPU. Cárguelos todos a la vez, resuélvalos todos a la vez, descargue los resultados de una vez. No tengo consejos específicos sobre el algoritmo, pero diré que las GPU son mejores con bucles que con ramas.
Michael Grant
1
@Michael C. Grant: Bueno, la sobrecarga de la comunicación puede ocultarse fácilmente en mi caso, por lo que no es un cuello de botella allí, estoy muy inclinado a usar BFGS de memoria limitada o BFGS estándar aquí, pero no estoy seguro si hay mejor enfoque
user0002128
Algunas personas implementaron LBFGS con CUDA .
BenC

Respuestas:

8

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.

LKlevin
fuente
0

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

Tolga Birdal
fuente
2
Levenberg-Marquart es para mínimos cuadrados no lineales. No creo que haya mencionado nada sobre mínimos cuadrados.
Kurt
0

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

Nikos M.
fuente