A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes

Consider a set {a₁, …, a_m, u, v} ⊂ ℝⁿ satisfying a mild nondegeneracy condition. When the polyhedron X = {x ∣ a₁^Tx ≤ 1, …, a_m^Tx ≤ 1} ⊂ ℝⁿ is orthogonally projected on the two-dimensional plane lin(u, v), then some of its vertices may be mapped on vertices of the two-dimensional image of X. These vertices of X will be called shadow vertices under that projection. Their number will be denoted by S.

This figure S has an outstanding relevance for the complexity of a special Simplex-Method, the dimension-by-dimension method, for solving LPs of the type

maximize  v^Tx

 s.t. a₁^Tx ≤ 1, …, a_m^Tx ≤ 1 where x, v, a₁, …, a_m ∈ ℝⁿ and m ≥ n.

This method applies the “shadow vertex algorithm” in n − 1 stages of increasing dimension, by constructing a Simplex-Path that visits only shadow vertices. In each stage specific versions of the vectors u and v are used to define the projection plane and to control the application of the “shadow vertex algorithm.” So S delivers an upper bound for the length of such a path in one stage.

We want to study the average-case complexity of these algorithms and are therefore interested in E_m,n(S), the expected value of S. For that purpose we assume a distribution of the linear programming problems corresponding to the rotation symmetry model (RSM):

The vectors a₁, …, a_m, u, v are distributed on ℝⁿ\{0} independently, identically and symmetrically under rotations.

In this paper we improve the upper bounds for E_m,n(S) from our polynomiality-proofs of 1982 and 1987. There we had found an upper bound of m^1/(n−1) · n³ · Const., valid for all RSM-distributions and all pairs (m ≥ n).

Based on a refined evaluation technique for space-angles, on a reorganization and on substantial modifications of the old proof, we are now able to confirm a bound

E_m,n(S) ≤ m^1/(n−1) · n² · Const. for all pairs (m,n) with m ≥ n.

This result had been desired since 1982, because then a bound m^1/(n−1) · n² · Const. had been derived exclusively for the situation, where n is fixed and m tends to infinity. All the time the question had been open, whether the asymptotical behaviour would be better than the behaviour in moderate dimensions, or whether the bound for the moderate case was crude.

In addition, we know—from an asymptotic analysis in 1987—that for a special RSM-distribution, namely the uniform distribution on the unit sphere, there is a lower bound for E_m,n(S) of type m^1/(n−¹⁾ · n² · Const. The combination of this result and the new upper bound shows that the new bound is sharp.