Resumen - Un límite inferior incondicional para el método del conjunto activo en la maximización cuadrática convexa

Un límite inferior incondicional para el método del conjunto activo en la maximización cuadrática convexa

2025-07-22 14:46:07

{"Eleon Bach","Yann Disser","Sophie Huiberts","Nils Mosis"}

{cs.DM,cs.CC,cs.DS,math.CO}

El artículo demuestra que el método del conjunto activo requiere un número exponencial de iteraciones en el peor de los casos para maximizar una función cuadrática convexa sujeta a restricciones lineales, independientemente de la regla de pivote utilizada. Este resultado mejora significativamente el mejor límite inferior conocido previamente y resuelve una pregunta abierta sobre si un grado constante es suficiente. Las contribuciones clave del artículo incluyen: - Demostrar un límite inferior exponencial para la maximización cuadrática convexa, mejorando el límite anterior de ω(log d) grados polinómicos para un límite superpolinomial y Ω(d) grados polinómicos para un límite exponencial. - Resolver una pregunta abierta sobre si un grado constante es suficiente para la maximización cuadrática convexa. - Construir una nueva formulación extendida utilizando productos deformados, lo cual podría ser de interés independiente. - Proporcionar un límite inferior unconditional para el método del conjunto activo, lo que es una contribución significativa al entendimiento de la complejidad de los algoritmos de programación lineal. La formulación extendida del artículo se construye mediante la aplicación recursiva de productos deformados a dos polígonos definidos por la función x^2 - x. La característica clave de esta formulación extendida es que su proyección en un plano da lugar a una aproximación poligonal de una parábola, preservando todos sus vértices exponenciales. El artículo luego muestra que el método del conjunto activo requiere un número exponencial de iteraciones para maximizar una función cuadrática convexa sobre la formulación extendida. Esto se hace construyendo una función de objetivo cuadrática convexa que fuerza al método del conjunto activo a seguir el borde parabólico de la proyección, sin permitir atajos a lo largo de arcos que corresponden a los bordes de la formulación extendida. En resumen, el artículo proporciona insights significativos sobre la complejidad del método del conjunto activo y hace una contribución mayor al entendimiento de la complejidad de los algoritmos de programación lineal.