Estoy utilizando el quadprog incorporado en Matlab para resolver un programa cuadrático con restricciones lineales. I vagamente recordaba de la escuela que la complejidad temporal de la programación cuadrática debe ser $O(n^3)$ y supongo que n se refiere al número de variables de decisión. Sin embargo, cuando calculo experimentalmente el tiempo de ejecución en función del número de variables en Matlab, el tiempo de ejecución en realidad aumenta menos que linealmente con más variables. Aumentar el número de variables de 10 a 100 sólo aumenta el tiempo de ejecución 5 veces. Estoy muy desconcertado por este resultado y tal vez lo que recordaba es erróneo. ¿Puede alguien arrojar algo de luz sobre la complejidad temporal de los programas cuadráticos en la teoría y en la práctica?
Respuestas
¿Demasiados anuncios?
Complejidad temporal de la programación cuadrática.
Vavasis demostró en 1991 que el programa cuadrático general es NP-duro, es decir, que tarda más de un tiempo polinómico en resolverse "exactamente" (en realidad, es imposible encontrar una solución exacta debido a la aritmética de precisión finita del ordenador). Si su QP es convexa, hay tiempo polinomial algoritmos de punto interior (por ejemplo Ye y Tse en 1989 publicó una extensión del algoritmo proyectivo de Karmarkar sobre programas cuadráticos convexos). Además, existen algoritmos de aproximación que devuelven soluciones locales de QP no convexos en tiempo de ejecución polinómico (p. ej. Ye, 1998 ).
Sobre la implementación interna de quadprog y la complejidad temporal.
Quadprog ejecuta un método de conjunto activo (de complejidad temporal exponencial para los peores casos de entrada) para una QP general. Para una QP realmente difícil (indefinida, con una matriz Q casi mal escalada), puede que no converja a una solución. En el caso de que la QP de entrada sea convexa, quadprog ejecuta un método de punto interior.
Nunca he comprobado la complejidad temporal de quadprog en la práctica, pero no se puede llegar a una inferencia simplemente observando los tiempos de ejecución a medida que se escala la dimensión de una QP dada. Es mejor generar un conjunto de pruebas, consistente en QP convexas y no convexas, elegir manualmente el algoritmo que quieres que quadprog ejecute para cada una de ellas, y observar los tiempos de ejecución.
No estoy familiarizado con los detalles de la función quadprog, pero creo que los problemas pueden ser más universales. La complejidad temporal cúbica es un límite asintótico en el peor de los casos. No significa que multiplicar por 10 cualquier problema vaya a multiplicar por 1000 el tiempo de ejecución. A menudo será menos, pero puede ser tan malo para algunos datos del problema.
En muchos algoritmos suele haber una "sobrecarga" de tiempo constante. La sobrecarga puede ser tan grande que el tiempo de ejecución es esencialmente independiente del tamaño del problema hasta cierto punto. El límite asintótico sólo es relevante cuando se comparan problemas grandes con problemas muy grandes. En su ejemplo, esto será difícil de observar porque los programas cuadráticos con miles o decenas de miles de variables pueden tardar horas o días en resolverse en un ordenador personal típico. La memoria puede convertirse en un problema, ya que los datos del problema crecen cuadráticamente con el número de variables.
Hay toda una industria dedicada a estos temas. Los solucionadores comerciales pueden costar decenas de miles de dólares. Para aplicaciones específicas, suelen utilizarse solucionadores especializados que explotan la estructura del problema. La dispersión de las matrices de entrada es la fuente más básica de mejoras en el tiempo de ejecución.
Los límites asintóticos del peor caso suelen ser una mala guía para resolver problemas prácticos. Además, son difíciles de verificar mediante simulaciones. Te sugiero que te dirijas a stackexchange, donde encontrarás discusiones detalladas sobre implementaciones de software de algoritmos concretos.
