{"ID":2891846,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.16648","arxiv_id":"2507.16648","title":"An unconditional lower bound for the active-set method in convex quadratic maximization","abstract":"We prove that the active-set method needs an exponential number of iterations in the worst-case to maximize a convex quadratic function subject to linear constraints, regardless of the pivot rule used. This substantially improves over the best previously known lower bound [IPCO 2025], which needs objective functions of polynomial degrees $ω(\\log d)$ in dimension $d$, to a bound using a convex polynomial of degree 2. In particular, our result firmly resolves the open question [IPCO 2025] of whether a constant degree suffices, and it represents significant progress towards linear objectives, where the active-set method coincides with the simplex method and a lower bound for all pivot rules would constitute a major breakthrough. Our result is based on a novel extended formulation, recursively constructed using deformed products. Its key feature is that it projects onto a polygonal approximation of a parabola while preserving all of its exponentially many vertices. We define a quadratic objective that forces the active-set method to follow the parabolic boundary of this projection, without allowing any shortcuts along chords corresponding to edges of its full-dimensional preimage.","short_abstract":"We prove that the active-set method needs an exponential number of iterations in the worst-case to maximize a convex quadratic function subject to linear constraints, regardless of the pivot rule used. This substantially improves over the best previously known lower bound [IPCO 2025], which needs objective functions of...","url_abs":"https://arxiv.org/abs/2507.16648","url_pdf":"https://arxiv.org/pdf/2507.16648v2","authors":"[\"Eleon Bach\",\"Yann Disser\",\"Sophie Huiberts\",\"Nils Mosis\"]","published":"2025-07-22T14:46:07Z","proceeding":"cs.DM","tasks":"[\"cs.DM\",\"cs.CC\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}