Mínimos cuadrados no lineales con restricciones de caja

10

¿Cuáles son las formas recomendadas de hacer mínimos cuadrados no lineales, min , con restricciones de recuadro ? Me parece (los tontos se apresuran) que uno podría hacer que las restricciones de la caja sean cuadráticas y minimizar $\sum err_i(p)^2$ $lo_j <= p_j <= hi_j$ donde es la "función tub" con forma de \ ___ /, . ¿Funciona esto en teoría, en la práctica? (Parece que hay muchos documentos teóricos sobre NLS +, pero mi interés es práctico: los casos de prueba reales o realistas me ayudarían a elegir entre los métodos).

\sum_{i} e r r_{i} (p)^{2} + C * \sum_{j} t u b (p_{j}, l o_{j}, h i_{j})^{2}

$\sum_i err_i(p)^2 + C * \sum_j tub( p_j, lo_j, hi_j )^2$

t u b (x, l o, h i)

$tub( x, lo, hi )$

m a x (l o - x, 0, x - h i)

$max( lo - x, 0, x - hi )$

(Expertos, agregue etiquetas: "mínimos cuadrados")

optimization constraints denis
fuente

55

Reemplazar restricciones estrictas con funciones de penalización es una técnica común en la optimización numérica. Parece que lo que está proponiendo es una forma particular de ese reemplazo. Puede leer todo sobre técnicas similares, por ejemplo, aquí: stanford.edu/~boyd/cvxbook

David Ketcheson el

p

$p$

p_{i} = min (max (l o_{j}, p_{j}^{'}), h i_{j})

$p_i=\min(\max(lo_j, p'_j),hi_j)$

11

Agregar términos de penalización al cuadrado para deshacerse de las restricciones es un enfoque simple que proporciona una precisión de orden 1 / factor de penalización solamente. Por lo tanto, no se recomienda para una alta precisión a menos que deje que la penalización se vaya al infinito durante el cálculo. Pero un alto factor de penalización hace que el Hesse esté muy mal condicionado, lo que limita la precisión total alcanzable sin tener en cuenta las restricciones explícitamente.

Tenga en cuenta que las restricciones vinculadas son mucho más fáciles de manejar que las restricciones generales, por lo que prácticamente nunca se convierten en sanciones.

El solucionador L-BFGS-B (usado con un historial de aproximadamente 5 dimensiones) generalmente resuelve problemas limitados limitados de manera muy confiable y rápida en ambas dimensiones altas y bajas. Las excepciones son la falta de convergencia en problemas que pueden volverse muy planos lejos de las soluciones, donde es fácil quedarse atrapado con un método de descenso.

Hicimos muchos experimentos en funciones muy diversas en muchas dimensiones diferentes, con muchos solucionadores diferentes disponibles, ya que necesitábamos un solucionador con restricciones limitadas muy robusto como parte de nuestro software de optimización global. L-BFGS-B se destaca claramente como método de propósito general, aunque, por supuesto, en los problemas de otros agentes de resolución funcionan significativamente mejor. Por lo tanto, recomendaría L-BFGS-B como primera opción, y probaría técnicas alternativas en caso de que L-BFGS-B maneje mal su clase particular de problemas.

Arnold Neumaier
fuente

L-BFGS está disponible en IPOPT, revisé mi respuesta.

Ali

5

Simplemente usaría el solucionador de PNL de propósito general IPOPT . Es el solucionador más robusto entre los que he probado.

A menos que tenga algunos requisitos muy especiales, no hay razón para insistir en un solucionador de problemas específico que solo funcione para NLS con restricciones de recuadro.

Un cambio en los requisitos (por ejemplo, agregar restricciones no lineales) causaría un gran dolor de cabeza con un solucionador específico del problema. No tendrá tales problemas si utiliza el IPOPT de uso general.

ACTUALIZACIÓN: puede probar L-BFGS con IPOPT , consulte bajo Cuasi-Newton en la documentación.

El procedimiento de solución puede ser más rápido a expensas de estropear la notable robustez de IPOPT. En mi opinión , use los derivados exactos si están disponibles. Comenzaría a jugar con aproximaciones (como L-BFGS) solo si tuviera problemas de rendimiento probados.

Ali
fuente

No sé qué tan bien funciona IPOPT, pero su sugerencia me recuerda declaraciones similares de los defensores del método de descenso simplex. Debido a que los mínimos cuadrados no lineales son una clase de problema común, rechazar directamente el uso de uno de los solucionadores de NLS existentes me parece un poco sospechoso.

Thomas Klimpel

@ThomasKlimpel Bueno, Denis debería darnos más detalles, entonces podríamos ayudarlo a elegir el solucionador adecuado. :) O puede comprobarlo por sí mismo y descubrir cuál se adapta mejor a sus necesidades. IPOPT parece ser un buen solucionador para empezar.

Ali

@ Ali, ¿puedes señalar algunos "casos de prueba reales o realistas" por favor?

denis

@denis podría pero no tengo intención de hacerlo, te sacaría de la pista. Lo único que importa es cómo IPOPT maneja su problema . A menos que tenga algunos requisitos muy especiales, debería resolverlo bien. IPOPT tiene interfaces para MATLAB, C ++, C, Fortran, R, AMPL, CUTEr. Elija una interfaz y pruebe lo que sucede con su problema :) Probar un solucionador de problemas específico tampoco sería más fácil.

Ali

@Thomas Klimpel, supongo que no estaba claro: no estoy rechazando, no preguntando sobre paquetes, sino preguntando por ideas o casos de prueba: ¿por qué este método trivial podría no funcionar bien?

denis

1

El paquete R minpack.lm CRAN proporciona una implementación de Levenberg-Marquardt con restricciones de cuadro.

En general, Levenberg-Marquardt es mucho más adecuado que L-BFGS-B para problemas de mínimos cuadrados. Convergerá (mucho) mejor en problemas desafiantes. También será mucho más rápido que el IPOPT de propósito general, ya que está diseñado para problemas de mínimos cuadrados no lineales.

El paquete R elige un enfoque de proyección muy sencillo para hacer cumplir las restricciones (ver el código fuente ). Dependiendo de la implementación de LM que esté utilizando, podría ser fácil de incluir.

Ahora, la sugerencia en los comentarios sobre el uso de una transformación (por ejemplo, una transformación sinusoidal como en scipy) también es una alternativa buena y simple para transformar su algoritmo LM sin restricciones en uno restringido. También deberá incluir la transformación en el jacobiano si el jacobiano es analítico.

jherek
fuente

0

(Años después) dos solucionadores que manejan las restricciones de la caja:

Scipy least_squares tiene 3 métodos, con un extenso documento:
1. 'trf': región de confianza reflexiva
2. 'dogbox'
3. 'lm': un contenedor heredado para MINPACK, sin restricciones de caja.
ceres

denis
fuente

1

Scipy dice explícitamente que el algoritmo Levenberg-Marquardt no puede manejar las restricciones de la caja.

tholy

Mínimos cuadrados no lineales con restricciones de caja

Respuestas: