Lower bounds for a subexponential optimization algorithm