java - simultaneas - sistemas de ecuaciones no lineales metodos numericos
Resolviendo numéricamente ecuaciones no lineales (5)
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 de 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:
Paquete de optimización no lineal de FPL Statistics Group Java . Esto incluye una traducción de Java de las rutinas clásicas de Fortran MINPACK.
JLAPACK , otra traducción de Fortran.
Alguna implementación de Python. Pure Python estaría bien, ya que se puede compilar en Java con jythonc.
¿Hay alguna heurística comúnmente utilizada para hacer la conjetura inicial que requiere LM?
En mi aplicación, necesito establecer algunas restricciones 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 opinion!
Actualización : Esto no es ciencia espacial, el número de parámetros a resolver (N) es como mucho 5 y los conjuntos de datos apenas son lo suficientemente grandes como para hacer posible la resolución, por lo que creo que Java es bastante eficiente para resolver esto. 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. Por ejemplo, Scipy.optimize.minpack.leastsq probablemente estaría bien si fuera Python puro.
En realidad, no he usado ninguna de esas bibliotecas de Java, así que tome esto como un grano de sal: en base a los backends probablemente miraría primero a JLAPACK. 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 debe usar una biblioteca C o Fortran bien optimizada en lugar de una Java pura, porque para grandes conjuntos de datos este tipo de tareas pueden consumir mucho tiempo.
Para crear la suposición inicial, realmente depende del tipo de función que intente encajar (y qué tipo de datos tiene). 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 calculé la media como solo average(values, weights = counts) , es decir, un promedio ponderado de los recuentos en el histograma, que era la media real del conjunto de datos. No era el centro exacto del pico que estaba buscando, pero se acercó lo suficiente, y el algoritmo se fue por 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 la comparación. 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 el principio ;-P así que creo que eres tú quien puede reírse de ellos ... bromeando. Tal vez).
Mientras más cerca esté su conjetura inicial de la solución, más rápido convergerá.
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 la 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.
No debe usar un solucionador no restringido si su problema tiene restricciones. Por ejemplo, si sabe que algunas de sus variables deben ser no negativas, debe decirle esto a su solucionador.
Si está contento de usar Scipy, le recomendaría scipy.optimize.fmin_l_bfgs_b. Puede colocar límites simples en sus variables con L-BFGS-B.
Tenga en cuenta que L-BFGS-B tiene una función objetivo general no lineal, no solo un problema de mínimos cuadrados no lineales.
El paquete FPL es bastante confiable, pero tiene algunas peculiaridades (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 el licenciamiento del código.
Buena suerte.
Estoy de acuerdo 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 usar el módulo scipy.optimize.fmin_l_bfgs_b de python 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 de L-BFGS -B algoritmo. Puede descargarlo desde http://www.mini.pw.edu.pl/~mkobos/programs/lbfgsb_wrapper y ver si coincide con sus necesidades.