Résumé - Un seuil inférieur inconditionnel pour la méthode de l'ensemble actif en maximisation quadratique convexe

Un seuil inférieur inconditionnel pour la méthode de l'ensemble actif en maximisation quadratique convexe

2025-07-22 14:46:07

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

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

Le papier prouve que la méthode de la base active nécessite un nombre exponentiel d'itérations dans le pire des cas pour maximiser une fonction quadratique convexe soumise à des contraintes linéaires, indépendamment de la règle de pivot utilisée. Ce résultat améliore considérablement la meilleure borne inférieure connue précédemment et résout une question ouverte sur la question de savoir si un degré constant est suffisant. Les contributions clés du papier incluent : - Montrer une borne inférieure exponentielle pour la maximisation quadratique convexe, améliorant la borne précédente de ω(log d) en degrés polynomiaux pour une borne super-polynomiale et Ω(d) en degrés polynomiaux pour une borne exponentielle. - Résoudre une question ouverte sur la question de savoir si un degré constant est suffisant pour la maximisation quadratique convexe. - Construire une formulation étendue nouvelle en utilisant des produits déformés, ce qui peut être d'intérêt indépendant. - Fournir une borne inférieure inconditionnelle pour la méthode de la base active, ce qui est une contribution significative à la compréhension de la complexité des algorithmes de programmation linéaire. La formulation étendue du papier est construite en appliquant récursivement des produits déformés à deux polygones définis par la fonction x^2 - x. La caractéristique clé de cette formulation étendue est que sa projection sur un plan donne une approximation polygonale d'une parabole tout en préservant tous ses sommets exponentiellement nombreux. Le papier montre ensuite que la méthode de la base active nécessite un nombre exponentiel d'itérations pour maximiser une fonction quadratique convexe sur la formulation étendue. Cela est fait en construisant une fonction d'objectif quadratique convexe qui force la méthode de la base active à suivre la frontière parabolique de la projection, sans permettre de raccourcis le long des arcs de cercle correspondant aux côtés de la formulation étendue. Dans l'ensemble, le papier fournit des insights significatifs sur la complexité de la méthode de la base active et apporte une contribution majeure à la compréhension de la complexité des algorithmes de programmation linéaire.