THE EXPECTED NUMBER OF EXTREME POINTS OF A RANDOM LINEAR PROGRAM Sancho E. Berenguer* Robert L. Smith** Technical Report 83-17 September, 1983 Revised July, 1984 *Instituto de Matematica Pura e Aplicada Rio de Janeiro 22460 Brasil **Department of Industrial and Operations Egnineering The University of Michigan Ann Arbor, Michigan 48109

THE EXPECTED NUMBER OF EXTREME POINTS OF A RANDOM LINEAR PROGRAM by Sancho E. Berenguer Robert L. Smith Instituto de Matematica Pura Department of Industrial e Aplicada and Operations Engineering Rio de Janeiro 22460 The University of Michigan Brasil Ann Arbor, Michigan 48109 Abstract There has been increasing attention recently on average case algorithmic performance measures since worst case measures can be qualitatively quite different. An important characteristic of a linear program, relating to Simplex Method performance, is the number of vertices of the feasible region, we show 2n to be an upper bound on the mean number of extreme points of a randomly generated feasible region with arbitrary probability distributions on the constraint matrix and right hand side vector. The only assumption made is that inequality directions are chosen in accordance with a series of independent fair coin tosses. 2

THE EXPECTED NUMBER OF EXTREME POINTS OF A RANDOM LINEAR PROGRAM Attempts to establish the mean number of extreme points and other topological properties of random linear constraint sets have included distribution dependent approaches (see, for example, Efron [1965], Liebling [1972], Schmidt and Mattheiss [1977], [1980]) as well as essentially distribution free approaches (May and Smith [1982], Adler and Berenguer [1981], [1983]). Apart from the purely mathematical interest of these models and results, they have proved useful in establishing average case performance of variants of the Simplex Method (Borgwardt [1982], Adler [1983], Saigal [1984], Smale [1983], Todd [1983]), Adler, Karp and Shamir [1982], Adler and Neggido [1983], and Haimovich [1983]). McMullen [1970] demonstrated that the worst case number of extreme points goes up factorially fast in problem dimension for the class of convex polytopes. Independently, May and Smith [1982] and Adler and Berenguer [1981], using the theory of arrangements of hyperplanes partitioning Euclidean space (Grunbaum [1967], Buck [1943]), established distribution invariant topological results for randomly generated linear constraint sets. They showed that the average number of extreme points for a class of distributions over convex polytopes increases only exponentially fast in problem dimension They assumed the generating distribution to be continuous, thus excluding sparsity, integer constraint coefficients, degeneracy, and other characteristics that real world and many randomly generated linear programs are known to possess. It was also assumed that inequality directions were decided on the basis of independent tosses of a fair coin. Retaining only the latter assumption, (now referred to as sign invariance) we show in this paper that for arbitrary distributions, the expected number of extreme points is bounded from above by 21 where n is the dimension of the constraint set. Note that this result for random linear programs does not exclude degeneracy. 3

1. A Model for Random Linear ProRrams We express the constraint sets in the general form Ax c b where A is an mxn matrix, b is co lumn m-vector and x is a column n-vector. The inequality directions are specified by a column m-vector e, where ei = 0 or 1 according to whether the ith constraint is c or 2 respectively. A probability distribution can then be specified over the space of all possible polyhedral sets S = (A,b,e) for n and m fixed. Let F1, F2 and F3 be the marginal distributions on A, b and e respectively. In particular define F3 by the m-tuple (P1, P2,..., P) where Pi = P(eiml) and el,e2,...em are assumed independent. Most of the occurrences of S correspond to empty polyhedral sets. We shall, however, be concerned with conditional properties of polyhedral sets so generated given that they are non-empty. After randomly generating the constraint set, we can obtain a region of dimension 0, 1,..., or n. Let Ek(m, n) denote the expected number of extreme points of a generated region of dimension k. Then the expected number of extreme points of a generated region of dimension n, n E(m, n) = k Ek(m, n) p(k), where p(k) is the probability of generating a region of dimension k. If Ek(m, k) 2k we would then have I n n E(m, n) - E0 (m, k) p(k)- k 2kp(k) 2n " p(k) 2k It suffices to show, without loss of generality, that En(m, n): 2n (we would clearly have that Ek(m, n) c 2k). In particular, we are interested in E(n,m) - the expected number of extreme points of a non-empty 4

polyhedral set formed by m constraints in Rn according to the model above. We shall impose the following restrictions. We require that pi=1/2 for i = 1,..., m in the m-tuple for F3; this is the crucial symmetry assumption of the main results of May and Smith [1982] and Adler and Berenguer [1981,1983]. We shall here extend the exponential bound of 2n for E(m,n) obtained in May and Smith [1982] and Adler and Berenguer [1981, 1983] by weakening the assumptions of F1 and F2 to arbitrary distributions over the constraint set matrix and right hand side vector respectively. Incidently their joint distribution is also allowed to be arbitrary. In keeping the one half symmetry on F3 we retain the assumption that each polyhedral set of the partition of Rn formed by the m hyperplanes is equally likely to occur as the chosen feasible region. 2. A Bound on the Expected Number of Extreme Points for an Arbitrary Number of Constraints TTheorem 1: Let Fl over A and F2 over b be arbitrary and possibly dependent distributions. Let ei,i = 1,2,...,m be i.i.d. Bernoulli random variables with Pi = 1/2 for all i = 1,..., m where e is independent of A and b. Then the expected number of extreme points for the corresponding randomly generated non-empty constraint set of m constraints and n variables, E(n,m) c 2n for all m and n. Before proving Theorem 1 we need the following results. Definitions (Winder [1966]): A set of k hyperplanes in Rn all passing through a common point is even-degenerate if the dimension of their intersection is of different parity than n - k. A set of hyperplanes that 5

is not even-degenerate is termed odd-degenerate. Lemma 1 (Winder [1966]): The number of regions in which m hyperplanes, all passing through some common point, divide Rn is equal to the number of distinct even-degenerate subsets of the given m hyperplanes minus the number of distinct odd-degenerate subsets (the empty subset is included and counted as even-degenerate). Lemma 2: Suppose a point p is determined by (that is, coincides with the intersection of) the distinct hyperplanes Hy,...,HP in Rn. Consider the hyperplane H I ^},...P, also passing through p and with the property that it does not contain any linear flat of dimension greater than zero which is the intersection of two or more of the H,j-=1,...,a. Let NH(p) be the number of regions (n-dimensional polyhedral sets) formed by the HP,j=l,...,9 and lying entirely in a distinguished half-space of H. Then NH(p) is invariant over all H satisfying the property above. Proof: It is sufficient to show that the number of even-degenerate and odd-degenerate sets of the partition of Rn by H,HB,...,HP is invariant to the choice of H, so long as it satisfies the property stated above. Then, from Lemma 1, the number of regions in the partition formed by H,...,HP and cut by H is invariant to H. The remaining uncut regions are then invariant in number, so that the half of these uncut regions lying wholly in a distinguished half-space is invariant in number. Let S =Hi PH fl... nHIP, where Hi P ( H..H. P}. It suffices to 11 i2 q'q ij show that the parity of H n S is invariant with respect to H. Let dim (S) - k 2 n-q. Clearly, dim (H n S) - k-l, for k > 0, by the property above that H satisfies. Also, dim (H n S) = 0 for k = 0; obviously, in this case H n s - s - p}. Therefore, parity of (Hn S) is invariant with respect to. f We can therefore simplify the notation substituting N(p) for NH_~)s 6

Lemma 3: Consider a point p determined in Rn by hyperplanes Hi,...,H. Let C(p) be the total number of regions formed by H,...,H around p. Then C(p) C 2nN(p). Proof: It can be easily seen that there must exist n linearly independent hyperplanes out of HP,...HP} which suffice to determine p. Without loss of generality denote these n hperplanes Hy,...,Hp. Now consider the 2n orthants determined by HP,...,HP and number them 1 through 2n. Let the number of regions in orthant i be Ci(i=1,...,2n). Then there clearly exists a hyperplane Hi, satisfying the property of Lemma 2, a half-space of which wholly contains the ith orthant. By Lemma 2, Ci c N(p) (i=1,...,2n) since every region in the orthant entirely lies in this distinguished halfspace of Hi. Hence it follows that 2n 2n C(p) = Z Ci C N(p) = 2nN(p). i=l i=l Now, consider the partition of Rn by the m hyperplanes of the constraint set Ax c b. We shall assume throughout that the m hyperplanes are distinct, for otherwise we simply embed the problem in the corresponding lower dimensional subspace. Let pr' r=l,2,...,k be the vertices of the partition (k is the number of vertices of the partition, kc ( )). Let H be a hyperplane in Rn, H+ a distinguished half-space of H and nP P H r and HPr the hyperplane parallel to H passing through Pr and the halfspace corresponding to HPr respectively. Since the number of hyperplanes in the partition is finite, we can find H such that HPr together with the hyperplanes H r that determine Pr on the partition (r = 1,..., r) have Jr 7

the property of Lemma 2.* By Lemma 2, exactly N(Pr) regions around Pr lie entirely in Hr, and we associate these regions to Pr. Also clearly no region R of the partition can be associated to two distinct points, say ps and Pt where s t. We can then state the following lemma whose proof is straightforward. Lemma 4: Consider the partition of space formed by m arbitrary hyperplanes k in Rn. Then the total number of regions in the partition N r N(pr) r= r where Pl,-..,pk are the points formed by the partition (the bound on the right is understood to be zero if there are no points). We can now easily prove Theorem 1, using the lemmas above. Proof of Theorem 1: E(m,n) = the expected number of extreme points for a randomly selected region of the partition = average of number of extreme k k points of regions of the partition = C(pr)/N Z 2nN(pr)/ N(pr)=2n. r=l r=l r=l (*) Let ai be the ith row of A corresponding to a normal of the ith hyperplane for i = l,...,m. Since the union of the spans of all subsets of a,...,am with n-i vectors or less cannot be all of Rn, there must exist a vector a E Rn that is not in the span of any subset of al,..,am of n-l vectors or less. Hence the solution set of ax = 0 (representing hyperplane H) cannot contain the intersection of the solution sets of any n-1 or less of the equations alx = 0,...,amx = 0. (**) Without loss of generality, HP+ C Pt and HP+t HPS, so that Pt + HpS But Pt E R and RcH *~ Contradiction. 8

3. Concluding Remarks The bound of 2n for the expected number of extreme points established in Theorem 1 is approached in the limit as the number of constraints increases for absolutely continuous independent distributions Fl and F2 as shown in May and Smith [1982], Adler and Berenguer [1981]. We suspect although we have not shown that all other topological properties also converge in the continuous case to those characteristic of an n-dimensional hypercube. Also since the proofs do not directly exploit the linearity of the varieties partitioning space, the same results can be expected for a wide class of nonlinear programs. The more interesting direction would be a weakening of the symmetry assumption on the inequality directions. Unfortunately, such a move would introduce strong distributional dependence of average topological properties on the particular choice for Fl and F2 as well as on their particular form of dependency. 9

References 1. I. Adler, "The Expected Number of Pivots Needed to Solve Parametric Linear Programs and the Efficiency of the Self-Dual Simplex Method", Working Paper, Industrial Engineering and Operations Research Department, University of California (Berkeley, CA, 1983). 2. I. Adler and S. E. Berenguer, "Random Linear Programs", Operations Research Center Report No. 81-4, University of California (Berkeley, CA, 1981). 3. I. Adler and S. E. Berenguer, "Generating Random Linear Programs", unpublished manuscript, Industrial Engineering and Operations Research Department, University of California (Berkeley, CA, 1983). (Submitted to Mathematical Programming). 4. I. Adler, R. M. Karp and R. Shamir, "A Simplex Variant Solving an m x d Linear Program in Expected Number of Pivots Depending on d Only", Report UCB CSD 83/157, Computer Science Division, University of California (Berkeley, CA, December, 1983). 5. I. Adler and N. Meggido, "A Simplex Algorithm Whose Average Number of Steps is Bounded Between two Quadratic Functions of the Smaller Dimension", unpublished manuscript (December, 1983). 6. K. H. Borgwardt, "Some Distribution - Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method", Mathematics of Operations Research 7(1982) 441-462. 7. R. C. Buck, "Partition of Space", American Mathematical Monthly 50(1943) 541-544. 8. B. Efron, "The Convex Hull to a Random Set of Points", Biometrika 52(1965) 331. 9. B. Grunbaum, Convex Polytopes (John Wiley and Sons, New York, 1967). 10

10. M. Haimovich, "The Simplex Algorithm is Very Good! On the Expected Number of Steps and Related Properties of Random Linear Programs", unpublished manuscript, Columbia University (New York, April 1983). 11. T. M. Liebling, "On the Number of Iterations of the Simplex Method", in: Henn, Kunzi, and Schubert, eds., Methods of Operations Research XVII (Sounderdruck, 1972) pp. 264-492. 12. J. H. May and R. L. Smith, "Random Polytopes: Their Definition, Generation, and Aggregate Properties", Mathematical Programming 24 (1982) 39-54. 13. P. McMullen, "The Maximum Number of Faces of a Convex Polytope", Mathematika 17(1970) 179-184. 14. R. Saigal, "A Variant that Solves Random Convex Quadratic Programs in Average Steps Bounded by a Quadratic Function of Size", Working Paper, Department of Industrial Engineering, Northwestern University (Evanston, IL, 1984). 15. B. K. Schmidt and T. H. Mattheiss, "The Probability that a Random Polytope is Bounded", Mathematics of Operations Research 2(1977) 292-296. 16. B. K. Schmidt and T. H. Mattheiss, "Computational Results on an Algorithm for Finding all Vertices of a Polytope", Mathematical Programming 18(1980) 308-329. 17. S. Smale, "The Problem of the Average Speed of the Simplex Method", Proceedings of the 11th International Symposium on Mathematical Programming, Universitat Bonn (Bonn, 1982) pp. 530-539. 11

18. M. J. Todd, "Polynomial Expected Behaviour of a Pivoting Algorithm for Linear Complementarity and Linear Programming Problems", Technical Report No. 595, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1983). 19. R. 0. Winder, "Partitions of N-space by Hyperplanes", Journal of SIAM Applied Mathematics 14(1966) 811-819. 12