← 研踪 PaperTrailarXiv:2507.16648 · v3
An Unconditional Lower Bound for the Active-Set Method in Almost-Linear Programming
首次提交 2025-07-22 22:46
版本更新 2026-10-27 23:19
雷达观测 2026-10-29 00:34
摘要
We prove that, for every fixed $ε\in(0,1]$, the active-set method requires exponentially many iterations in the worst case to maximize a convex objective of the form $(x_1)^{1+ε}+\vec c^{\top}\vec x$ subject to linear constraints, regardless of the pivot rule used. Our lower bound therefore holds for objectives arbitrarily close to the linear case $ε=0$, where the active-set method coincides with the simplex method and a lower bound for all pivot rules would constitute a major breakthrough. The special case $ε=1$ yields a lower bound in convex quadratic maximization. This improves on the best previously known lower bound [IPCO 2025] requiring polynomial objectives of degree $ω(\log d)$ in dimension $d$ and firmly resolves the open question of whether a constant degree suffices. 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 convex objective with a single non-linear variable 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-10-27 23:19 · 最新观测版本
An Unconditional Lower Bound for the Active-Set Method in Almost-Linear Programming
We prove that, for every fixed $ε\in(0,1]$, the active-set method requires exponentially many iterations in the worst case to maximize a convex objective of the form $(x_1)^{1+ε}+\vec c^{\top}\vec x$ subject to linear constraints, regardless of the pivot rule used. Our lower bound therefore holds for objectives arbitrarily close to the linear case $ε=0$, where the active-set method coincides with the simplex method and a lower bound for all pivot rules would constitute a major breakthrough. The special case $ε=1$ yields a lower bound in convex quadratic maximization. This improves on the best previously known lower bound [IPCO 2025] requiring polynomial objectives of degree $ω(\log d)$ in dimension $d$ and firmly resolves the open question of whether a constant degree suffices. 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 convex objective with a single non-linear variable 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.
查看此版本解读 →查看此版本原文 ↗