The simplex method. A probabilistic analysis
Research exposition (monographs, survey articles) pertaining to calculus of variations and optimal control (49-02) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Linear programming (90C05)
This is the book that researchers interested in the average analysis of the computational complexity of pivotal methods for linear programming have been waiting for. The author received the prestigious Lancaster award (1982) of the OR society of America for his pioneering work in this area, and announced his intention of writing the book at that time. Many variants of the simplex method for linear programming have been shown to exhibit exponential growth in computational requirements on classes of instances specially constructed by mathematicians to bring out their worst behavior. However, the simplex method and other variants of it, turned out to be extremely efficient mathematical tools for solving real world linear programming problems in extensive use by numerous practitioners all over the world over the last 40 years. This tremendous discrepancy between the bad worst case behavior, and the good behavior on real world problems has always fascinated mathematicians. The lure of average analysis is to provide a mathematical explanation of this intriguing phenomenon. This is the first book in this area of research. The title is somewhat misleading. What is analyzed is not the usual simplex method that one sees in many papers and books in the literature, but a parametric variant of it called the shadow vertex method developed by the author. Of course, this criticism can be levelled against several publications in this area. As far as I know, no one has carried out an average analysis of the usual simplex method yet. What have been analyzed are parametric or self-dual parametric variants of the simplex method. Nobody knows what an appropriate probabilistic model is for real world linear programming problems. The problem analyzed in this book is of the form: find \(x\in R^ n\) that maximizes \(v^ Tx\), subject to \(a^ T_ ix\leq 1\), \(i=1\) to m, where \(m\geq n\); and the data, \(v,a_ 1,...,a_ m\) are all column vectors in \(R^ n\setminus \{0\}\), distributed independently, identically and symmetrically under rotations. There are two major weakeness of this probabilistic model. One is that it assigns probability zero to the set of degenerate problems. Many real world problems tend to have lots of zeros in the coefficient matrix, and to be degenerate. Another is that it makes the expected value of every data element to be zero, an unreasonable assumption for real world models, since we cannot get something for nothing. The analysis under more realistic probabilistic models is a field for future research. The book begins with an introductory chapter in which the motivation for carrying out the average analysis of pivotal methods for linear programming is clearly developed, and all the results obtained by researchers so far are summarized briefly. The next chapter describes the shadow vertex algorithm. This is followed by a lengthy treatment of the analysis of the average number of pivot steps, and proofs of polynomial boundedness of this number. The proofs are of course highly technical and involve many frightening quotients. In a final chapter, the analysis has been extended to the linear program involving nonnegativity constraints on all the variables, in addition to those mentioned earlier. This book is a welcome addition to the mathematical literature on linear programming. After some years of very intense activity by several researchers, there is now a period of lull in this area. The publication of this book would hopefully awaken interest in this area and draw new researchers into it, so that the ultimate good of giving a satisfactory mathematical explanation of the good behavior of the simplex method on real world problems can be completed soon.
- scientific article; zbMATH DE number 4197740
- scientific article; zbMATH DE number 3898607
- A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
- How fast does the simplex method usually work? Or: the search for (stochastic) independence
- New results on the average behavior of simplex algorithms
- Linear programming with spheres and hemispheres of objective vectors
- Pivot rules for linear programming: A survey on recent theoretical developments
- A strictly improving linear programming Phase I algorithm
- A finite algorithm for solving general quadratic problems
- Linear programming, the simplex algorithm and simple polytopes
- Criss-cross methods: A fresh view on pivot algorithms
- Average number of iterations of some polynomial interior-point -- algorithms for linear programming
- Credal ensembles of classifiers
- Series associated to some expressions involving the volume of the unit ball and applications
- Estimating support functions of random polytopes via Orlicz norms
- Monotonicity properties of the volume of the unit ball in \({\mathbb{R}^{n}}\)
- Frontiers of sphere recognition in practice
- New bounds and asymptotic expansions for the volume of the unit ball in \(\mathbb{R}^n\) based on Padé approximation
- Schwarz-Pick lemma for harmonic and hyperbolic harmonic functions
- A linear programming primer: from Fourier to Karmarkar
- How fast does the simplex method usually work? Or: the search for (stochastic) independence
- Iterative computation of security strategies of matrix games with growing action set
- Moser's shadow problem
- Optimizing MSE for clustering with balanced size constraints
- Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
- Inequalities for the volume of the unit ball in \(\mathbb R^n\)
- Convex geometry and its applications. Abstracts from the workshop held December 12--18, 2021 (hybrid meeting)
- Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
- New results on the average behavior of simplex algorithms
- scientific article; zbMATH DE number 3880432 (Why is no real title available?)
- Volume of unit ball in an n-dimensional normed space and its asymptotic properties
- A parallel approach for determining confidence intervals of variable statistics in large and sparse linear equations with RHS ranges
- scientific article; zbMATH DE number 3898607 (Why is no real title available?)
- Implementing the simplex method as a cutting-plane method, with a view to regularization
- A path-following method for finding multiple equilibrium points in cellular neural networks
- Sharp inequalities for the digamma and polygamma functions
- A counterexample to the Hirsch conjecture
- Universality for Eigenvalue Algorithms on Sample Covariance Matrices
- Some properties of the gamma and psi functions, with applications
- scientific article; zbMATH DE number 764392 (Why is no real title available?)
- On the variance of the number of pivot steps required by the simplex algorithm
- scientific article; zbMATH DE number 803180 (Why is no real title available?)
- The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model
- A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
- The Ahlfors-Schwarz lemma, curvature, distance and distortion
- scientific article; zbMATH DE number 4197740 (Why is no real title available?)
- Random projections for linear programming
- Book Review: The basic George B. Dantzig
- A generalized simplex method for integer problems given by verification oracles
- Sharp inequalities related to the volume of the unit ball in \(\mathbb{R}^n\)
- The Polyhedral Geometry of Pivot Rules and Monotone Paths
- Monotone paths on cross-polytopes
- A spectral Bernstein theorem
- The average computing time of the simplex method in a generalized rotational symmetry model
- Linear optimization with the shadow vertex algorithm in the context of probabilistic analyses. Studies on the transition from phase 1 to phase 2 in the average-case analysis and in the smoothing analysis of the simplex method
- Upper and lower bounds on the smoothed complexity of the simplex method
- Hyperelliptic integrals and special functions for the spatial variational problem
- A spectral approach to polytope diameter
- Inequalities and asymptotic expansions related to the volume of the unit ball in \(\mathbb{R}^n\)
- Upper and lower bounds on the smoothed complexity of the simplex method
- On the number of degenerate simplex pivots
- On the number of degenerate simplex pivots
- On the shadow simplex method for curved polyhedra
- Asymptotic bounds on the combinatorial diameter of random polytopes
- Pivot polytopes of products of simplices and shuffles of associahedra
- Unimodality of the number of paths per length on polytopes: examples, counterexamples, and a central limit theorem
- S-hypersimplices, pulling triangulations, and monotone paths
- Simplex-inspired algorithms for solving a class of convex programming problems
This page was built for publication: The simplex method. A probabilistic analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083366)
