In this paper we derive a lower bound on the average complexity of the Simplex-Method as a solution-process for linear programs (LP) of the type: maximize vT x subject to aT1 x ≤ 1, …, aTm x ≤ 1. We assume these problems to be randomly generated according to the Rotation-Symmetry-Model: Let a1, …, am, v be distributed independently, identically and symmetrically under rotations on ℝn\{0}. We concentrate on distributions over ℝn with bounded support and we do our calculations only for a subfamily of such distributions, which provides computability and is representative for the whole set of these distributions. The Simplex-Method employs two phases to solve such an LP. In Phase I it determines a vertex x0 of the feasible region – if there is any. In Phase II it starts at x0 to generate a sequence of vertices x0, …, xs such that successive vertices are adjacent and that the objective vT xi increases. The sequence ends at a vertex xs which is either the optimal vertex or a vertex exhibiting the information that no optimal vertex can exist. The precise rule for choosing the successor-vertex in the sequence determines a variant of the Simplex-Algorithm. We can show for every variant, that the expected number of steps svar for a variant, when m inequalities and n variables are present, satisfies Em,n[svar] ≥ const. m1/(n–1)n0 for all pairs m ≥ n and for all variants.
