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 (Q6486814)

For practical applications, by far the most useful optimization algorithm for solving linear programs is the celebrated simplex algorithm. In spite of its spectacular performance on real world problems, it is still not known whether a specific version exists which requires only a polynomial number of iterations; indeed, pathological examples requiring exponentially many iterations have been constructed for most known pivoting rules. The well-known work by Karl Heinz Borgwardt and his students (started in the mid-seventies) went a long way to explaining this discrepancy between theory and practice by showing that the expected number of iterations is indeed polynomial in the number \(m\) of restrictions and the number \(d\) of variables for a specific version of the simplex method, namely the shadow vertex algorithm (under suitable assumptions on the probability distribution for the input data): for general dimension pairs \((m,d)\) the expected number is less than \(O\big(d^3 m^{ \frac{1}{d-1}}\big)\) and in the asymptotic case \(m \to \infty\) (for fixed \(d\)) only \(O\big(d^{\frac{5}{2}} m^{ \frac{1}{d-1}}\big)\) iterations occur on the average.NEWLINENEWLINEIn 2001, Spielman and Teng suggested a different approach: the \textit{smoothed analysis}. While Borgwardt's average case analysis establishes that the bad instances are rare considered over all possible (standardized) inputs, the aim of this more recent approach is to show that the good instances by far outweigh the bad ones even if one restricts attention to instances close to any given (possibly very bad) instance. Technically, one considers a perturbation of the given data under a Gaussian distribution and then estimates the expected number of iterations depending on \(m\), \(d\) and the standard deviation \(\sigma\) of the Gaussian distribution. With an extremely involved analysis, Spielman and Teng could indeed obtain a polynomial bound of roughly \(O(m^{86}d^{55}\sigma^{-30})\) iterations, which was later improved by Vershynin who established a bound of \(O\big(\max \big\{d^5(\ln m)^2 , d^9(\ln d)^4, d^3\sigma^{-4}\big\}\big)\) iterations. These results again deal with the shadow vertex algorithm.NEWLINENEWLINEHowever, up to now this smoothed analysis is not entirely satisfactory, as it does not really apply to the shadow vertex algorithm per se but rather to a randomized version. This was necessary for the application of the fundamental results of the authors mentioned above for one run of the shadow vertex algorithm (i.e., for Phase II). These results are based on the condition that one starts at a vertex optimal for an auxiliary objective function given by a vector \(u\), which has to be chosen stochastically independent of the input data \(A\) and \(b\). Unfortunately, the usual Phase I methods violate this condition. At this point randomization came into play in order to make application nevertheless possible; for instance, Vershynin added \(d\) further artificial restrictions to force a suitable starting vertex compatible with \(u\) in order to be able to use a normal distribution for \(u\). However, in general, this will not result in an optimal solution for the original problem, so that he had to use this approach several times to finally succeed. Therefore, it is not quite clear whether the bound mentioned above arises from the smoothing, or from randomizing the starting vertex as just described. In particular, no real comparison to complexity results about algorithms which surely solve the problem is possible in this way, as the smoothed analysis deals with a randomized instead of a deterministic algorithm.NEWLINENEWLINEThe breakthrough obtained in the dissertation under review lies in clarifying the situation: with a slightly worse estimate on the number of iterations, namely \(O\big(\max \big\{d^6(\ln m)^2 , d^4\sigma^{-4}\big\}\big),\) Schnalzger finally achieves the smoothed analysis of a truly deterministic version of the shadow vertex algorithm already used by Borgwardt, the so-called dimension-by-dimension algorithm. This algorithm treats the problem in \(d\) sequential stages, where in each stage \(k=1, \dots, d\) the corresponding \(k\)-dimensional problem is solved. The solution of stage \(k\) delivers a starting vertex for stage \(k+1\). Schnalzger shows that in stage \(k\) the \(k\)-th unit vector can be used in place of \(u\), and this unit vector does not depend on the input data. The extra factor of (essentially) \(d\) in the estimate is due to the fact that this variant has to use the shadow vertex approach in \(d\) stages, beginning with a 2-dimensional restricted problem and adding one dimension at each stage. Again, the proof is technically very involved, in spite of making use of Vershynin's results. In particular, the author had to find a sufficiently strong estimate for the expected number of shadow vertices in the case \(d=2\), which was not covered by Vershynin's work.NEWLINENEWLINEThe Ph.D. thesis under review also contains an excellent overview of the previous work in the area, as well as an experimental study of how much the stochastic dependencies arising in a direct application of the shadow vertex algorithm (which would seem preferable in practical applications) really influence the expected number of iterations. The extensive tests indicate that the expected number of iterations needed in phase II is then in most cases even slightly less than for the theoretical version discussed before.NEWLINENEWLINEIn this reviewer's opinion, Schnalzger's work constitutes a real breakthrough in our understanding of the average behavior of the simplex method, and it would be very desirable to have these important results available in an English version.