Resolviendo numéricamente ecuaciones no lineales

Question

Necesito resolver problemas de minimización no lineal (mínimos cuadrados residuales de N incógnitas) en mi programa Java. La forma habitual de resolver estos es el algoritmo Levenberg-Marquardt. Tengo un par de preguntas

• ¿Alguien tiene experiencia en las diferentes implementaciones de LM disponibles? Existen sabores ligeramente diferentes de LM, y he oído que la implementación exacta del algoritmo tiene un efecto importante en la estabilidad numérica. Mis funciones se comportan muy bien, así que esto probablemente no sea un problema, pero por supuesto me gustaría elegir una de las mejores alternativas. Aquí hay algunas alternativas que he encontrado:

  • FPL Statistics Group's Nonlinear Optimization Java Package. Esto incluye una traducción de Java de las rutinas clásicas de Fortran MINPACK.

  • JLAPACK, otra traducción de Fortran.

  • Optimization Algorithm Toolkit.

  • Javanumerics.

  • Implementación de Python. Pure Python estaría bien, ya que se puede compilar en Java con jythonc.

• ¿Hay alguna heurística de uso común para hacer la conjetura inicial que requiere LM?

• En mi aplicación necesito establecer algunas limitaciones en la solución, pero afortunadamente son simples: solo requiero que las soluciones (para ser soluciones físicas) no sean negativas. Las soluciones levemente negativas son el resultado de imprecisiones de medición en los datos, y obviamente deben ser cero. Estaba pensando en utilizar LM "normal" pero repetir para que, si algunas de las incógnitas se vuelven negativas, lo ajuste a cero y resuelva el resto de eso. Los matemáticos reales probablemente se reirán de mí, pero ¿creen que esto podría funcionar?

¡Gracias por cualquier opinión!

Actualización: Esto no es ciencia espacial, el número de parámetros a resolver (N) es como máximo 5 y los conjuntos de datos son apenas lo suficientemente grandes como para hacer posible la resolución, así que creo que Java es bastante eficiente para resolver esta. Y creo que este problema ha sido resuelto en numerosas ocasiones por los matemáticos aplicados inteligentes, por lo que estoy buscando una solución preparada en lugar de cocinar la mía. P.ej. Scipy.optimize.minpack.leastsq probablemente estaría bien si fuera Python puro ...

Answer 1

No he usado realmente ninguna de esas bibliotecas Java, así que tómenlo con un grano de sal: en función de los backends probablemente me vería en JLAPACK primero. Creo que LAPACK es el back-end de Numpy, que es esencialmente el estándar para hacer álgebra lineal/manipulaciones matemáticas en Python. Al menos, definitivamente debería usar una biblioteca C o Fortran bien optimizada en lugar de Java pura, porque para grandes conjuntos de datos este tipo de tareas puede consumir mucho tiempo.

Para crear la suposición inicial, realmente depende del tipo de función que intentas encajar (y qué tipo de datos tienes). Básicamente, solo busque un cálculo relativamente rápido (probablemente O (N) o mejor) que le dará un valor aproximado para el parámetro que desee.(Hace poco hice esto con una distribución gaussiana en Numpy y estimé que la media era solo average(values, weights = counts), es decir, un promedio ponderado de los recuentos en el histograma, que era el verdadero promedio del conjunto de datos. No era el centro exacto del pico que estaba buscando, pero se acercó lo suficiente, y el algoritmo fue el resto del camino.)

En cuanto a mantener las restricciones positivas, su método parece razonable. Ya que está escribiendo un programa para hacer el trabajo, tal vez solo cree una bandera booleana que le permita habilitar o deshabilitar fácilmente el comportamiento "forzar-no-negativo" y ejecutarlo en ambos sentidos para comparar. Solo si obtiene una gran discrepancia (o si una versión del algoritmo tarda demasiado), puede ser algo de qué preocuparse. (Y los matemáticos REALES harían una minimización de mínimos cuadrados analíticamente, desde cero ;-P así que creo que eres tú quien puede reírse de ellos ... bromeando. Tal vez)

Answer 2

Cuanto más cerca estés de adivinar la solución, más rápido convergerás.

Dijiste que era un problema no lineal. Puede hacer una solución de mínimos cuadrados linealizada. Tal vez puedas usar esa solución como una primera suposición. Algunas iteraciones no lineales le dirán algo acerca de cuán buena o mala es una suposición.

Otra idea sería probar otro algoritmo de optimización. Los algoritmos de colonia genética y de hormigas pueden ser una buena opción si puede ejecutarlos en muchas CPU. Tampoco requieren derivadas continuas, por lo que son agradables si tiene datos discretos y discontinuos.

Answer 3

No debe usar un solucionador no restringido si su problema tiene limitaciones. Para el caso si sabe que algunas de sus variables no deben ser negativas, debe indicarlo al al solucionador.

Si está contento de utilizar Scipy, recomendaría scipy.optimize.fmin_l_bfgs_b Puede poner límites simples en sus variables con L-BFGS-B.

Tenga en cuenta que L-BFGS-B tiene una función objetivo no lineal general, no solo un problema de mínimos cuadrados no lineales.

Answer 4

El paquete FPL es bastante confiable pero tiene algunos caprichos (el acceso a la matriz comienza en 1) debido a su interpretación muy literal del antiguo código fortran. El método LM en sí mismo es bastante confiable si su función se comporta bien. Una forma simple de forzar restricciones no negativas es usar el cuadrado de parámetros en lugar de los parámetros directamente. Esto puede presentar soluciones espurias, pero para modelos simples, estas soluciones son fáciles de eliminar.

Hay un código disponible para un método LM "restringido". Mire aquí http://www.physics.wisc.edu/~craigm/idl/fitting.html para mpfit. Hay una pitón (desafortunadamente se basa en Numeric) y una versión C. El método LM tiene alrededor de 1500 líneas de código, por lo que podría inclinarse a portar el C a Java. De hecho, el método LM "restringido" no es muy diferente al método que visualizó. En mpfit, el código ajusta el tamaño del paso relativo a los límites en las variables. También he tenido buenos resultados con mpfit.

No tengo mucha experiencia con BFGS, pero el código es mucho más complejo y nunca he tenido claro la licencia del código.

Buena suerte.

Answer 5

Acepto con codehippo; Creo que la mejor manera de resolver problemas con restricciones es usar algoritmos diseñados específicamente para manejarlos. El algoritmo L-BFGS-B probablemente sea una buena solución en este caso.

Sin embargo, si usa scipy.optimize de python.El módulo fmin_l_bfgs_b no es una opción viable en su caso (porque está usando Java), puede intentar usar una biblioteca que he escrito: un contenedor Java para el código Fortran original del algoritmo L-BFGS-B. Puede descargarlo desde http://www.mini.pw.edu.pl/~mkobos/programs/lbfgsb_wrapper y ver si coincide con sus necesidades.