An Unconditional Lower Bound for the Active-Set Method in Almost-Linear Programming

Eleon Bach, Yann Disser, Sophie Huiberts +1

We prove that, for every fixed $\epsilon \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+ε}+\…