A friendly smoothed analysis of the simplex method. (English) Zbl 1451.90095
Summary: Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for understanding the simplex method was given by D. A. Spielman and S.-H. Teng [J. ACM 51, No. 3, 385–463 (2004; Zbl 1192.90120)] who developed the notion of smoothed analysis. Starting from an arbitrary linear program (LP) with \(d\) variables and \(n\) constraints, Spielman and Teng [loc. cit.] analyzed the expected runtime over random perturbations of the LP, known as the smoothed LP, where variance \(\sigma^2\) Gaussian noise is added to the LP data. In particular, they gave a two-stage shadow vertex simplex algorithm which uses an expected \(\widetilde{O}(d^{55} n^{86} \sigma^{-30} + d^{70}n^{86})\) number of simplex pivots to solve the smoothed LP. Their analysis and runtime was substantially improved by A. Deshpande and D. A. Spielman [“Improved smoothed analysis of the shadow vertex simplex method”, in: Proceddings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), Pittsburgh, PA, 349–356 (2005; doi:10.1109/SFCS.2005.44)] and later R. Vershynin [SIAM J. Comput. 39, No. 2, 646–678 (2009; Zbl 1200.68128)]. The fastest current algorithm, due to Vershynin, solves the smoothed LP using an expected \(O\big(\log^2 n \cdot \log\log n \cdot (d^3\sigma^{-4} + d^5\log^2 n + d^9\log^4 d)\big)\) number of pivots, improving the dependence on \(n\) from polynomial to polylogarithmic. While the original proof of Spielman and Teng [loc. cit.] has now been substantially simplified, the resulting analyses are still quite long and complex and the parameter dependencies far from optimal. In this work, we make substantial progress on this front, providing an improved and simpler analysis of shadow simplex methods, where our algorithm requires an expected \(O(d^2 \sqrt{\log n} ~ \sigma^{-2} + d^3 \log^{3/2} n)\) number of simplex pivots. We obtain our results via an improved shadow bound, key to earlier analyses as well, combined with improvements on algorithmic techniques of Vershynin. As an added bonus, our analysis is completely modular and applies to a range of perturbations, which, aside from Gaussians, also includes Laplace perturbations.
MSC:
| 90C05 | Linear programming |
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
| 68W40 | Analysis of algorithms |
References:
| [1] | K. A. Adiprasito and B. Benedetti, The Hirsch conjecture holds for normal flag complexes, Math. Oper. Res., 39 (2014), pp. 1340-1348, https://doi.org/10.1287/moor.2014.0661. · Zbl 1319.52017 |
| [2] | I. Adler, The Expected Number of Pivots Needed to Solve Parametric Linear Programs and the Efficiency of the Self-Dual Simplex Method, Technical report, Department of IE and OR, University of California, 1983. |
| [3] | I. Adler, R. M. Karp, and R. Shamir, A simplex variant solving an \(m\times d\) linear program in \(O({min}(m^2, d^2))\) expected number of pivot steps, J. Complexity, 3 (1987), pp. 372-387, https://doi.org/10.1016/0885-064X(87)90007-0. · Zbl 0641.65054 |
| [4] | I. Adler and N. Megiddo, A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, J. ACM, 32 (1985), pp. 871-895. · Zbl 0634.65044 |
| [5] | N. Amenta and G. M. Ziegler, Deformed products and maximal shadows, Contemp. Math., 223 (1998), pp. 57-90. · Zbl 0916.90205 |
| [6] | D. Arthur, B. Manthey, and H. Röglin, Smoothed analysis of the \(k\)-means method, J. ACM, 58 (2011), 19, https://doi.org/10.1145/2027216.2027217. · Zbl 1281.68224 |
| [7] | D. Avis and V. Chvátal, Notes on Bland’s Pivoting Rule, in Polyhedral Combinatorics, Springer, New York, 1978, pp. 24-34. · Zbl 0403.65025 |
| [8] | M. L. Balinski, The Hirsch conjecture for dual transportation polyhedra, Math. Oper. Res., 9 (1984), pp. 629-633, https://doi.org/10.1287/moor.9.4.629. · Zbl 0555.90071 |
| [9] | K. Ball, An elementary introduction to modern convex geometry, Flavors of Geometry, 31 (1997), pp. 1-58. · Zbl 0901.52002 |
| [10] | D. Barnette, An upper bound for the diameter of a polytope, Discrete Math., 10 (1974), pp. 9-13. · Zbl 0294.52007 |
| [11] | R. E. Bixby, A brief history of linear and mixed-integer programming computation, Doc. Math., (2012), pp. 107-121. · Zbl 1270.90003 |
| [12] | R. E. Bixby, M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling, MIP: Theory and practice-Closing the gap, in System Modelling and Optimization, Kluwer Academic, Boston, MA, 2000, pp. 19-49. · Zbl 0986.90025 |
| [13] | W. Blaschke, INTEGRALGEOMETRIE 2, Bulletin mathématique de la Société Roumaine des Sciences, 37 (1935), pp. 3-11. · JFM 61.0763.01 |
| [14] | N. Bonifas, M. Di Summa, F. Eisenbrand, N. Hähnle, and M. Niemeier, On sub-determinants and the diameter of polyhedra, Discrete Comput. Geom., 52 (2014), pp. 102-115, https://doi.org/10.1007/s00454-014-9601-x. · Zbl 1310.52013 |
| [15] | T. Bonnesen and W. Fenchel, Theory of Convex Bodies, BCS Associates, 1987. · Zbl 0628.52001 |
| [16] | K.-H. Borgwardt, Untersuchungen zur Asymptotik der mittleren Schrittzahl von Simplexverfahren in der linearen Optimierung, Ph.D. thesis, Universität Kaiserslautern, 1977. · Zbl 0416.90041 |
| [17] | K.-H. Borgwardt, The average number of pivot steps required by the simplex-method is polynomial, Z. Oper. Res. Ser. A-B, 26 (1982), pp. A157-A177. · Zbl 0488.90047 |
| [18] | K.-H. Borgwardt, The Simplex Method: A Probabilistic Analysis, Algorithms Combin., Springer, Berlin, 1987. · Zbl 0634.90042 |
| [19] | K.-H. Borgwardt, A sharp upper bound for the expected number of shadow vertices in LP-polyhedra under orthogonal projection on two-dimensional planes, Math. Oper. Res., 24 (1999), pp. 544-603, https://doi.org/10.1287/moor.24.3.544. · Zbl 0967.90079 |
| [20] | K.-H. Borgwardt, A sharp upper bound for the expected number of shadow vertices in LP-polyhedra under orthogonal projection on two-dimensional planes, Math. Oper. Res., 24 (4) (1999), pp. 925-984, https://doi.org/10.1287/moor.24.3.544. · Zbl 0977.90020 |
| [21] | S. Borgwardt, J. A. De Loera, and E. Finhold, The diameters of network-flow polytopes satisfy the Hirsch conjecture, Math. Program., 171 (2018), pp. 283-309, https://doi.org/10.1007/s10107-017-1176-x. · Zbl 1406.52023 |
| [22] | G. Brightwell, J. van den Heuvel, and L. Stougie, A linear bound on the diameter of the transportation polytope, Combinatorica, 26 (2006), pp. 133-139, https://doi.org/10.1007/s00493-006-0010-5. · Zbl 1150.90008 |
| [23] | T. Brunsch, K. Cornelissen, B. Manthey, H. Röglin, and C. Rösner, Smoothed analysis of the successive shortest path algorithm, SIAM J. Comput., 44 (2015), pp. 1798-1819, https://doi.org/10.1137/140989893. · Zbl 1326.05039 |
| [24] | T. Brunsch, A. Großwendt, and H. Röglin, Solving totally unimodular LPs with the shadow vertex algorithm, in Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science, STACS ‘15, 2015. · Zbl 1355.68114 |
| [25] | D. Dadush and N. Hähnle, On the shadow simplex method for curved polyhedra, Discrete Comput. Geom., 56 (2016), pp. 882-909, https://doi.org/10.1007/s00454-016-9793-3. · Zbl 1377.90055 |
| [26] | D. Dadush and S. Huiberts, A friendly smoothed analysis of the simplex method, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 390-403. · Zbl 1427.90199 |
| [27] | D. Dadush and S. Huiberts, Smoothed analysis of the simplex method, in Beyond the Worst-Case Analysis of Algorithms, T. Roughgarden, ed., Cambridge University Press, Cambridge, expected November 2020. · Zbl 1427.90199 |
| [28] | V. Damerow and C. Sohler, Extreme Points Under Random Noise, in Proceedings of the European Symposium on Algorithms, Springer, New York, 2004, pp. 264-274. · Zbl 1111.68722 |
| [29] | G. B. Dantzig, Programming in a Linear Structure, Technical report, U.S. Air Force Comptroller, USAF, Washington, DC, 1948. |
| [30] | G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, in Activity Analysis of Production and Allocation, Cowles Commission Monogr. 13, Wiley, New York, 1951, pp. 339-347. · Zbl 0045.09802 |
| [31] | G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1959. |
| [32] | J. A. De Loera, E. D. Kim, S. Onn, and F. Santos, Graphs of transportation polytopes, J. Combin. Theory Ser. A, 116 (2009), pp. 1306-1325, https://doi.org/10.1016/j.jcta.2009.03.010. · Zbl 1229.05190 |
| [33] | A. Deshpande and D. A. Spielman, Improved smoothed analysis of the shadow vertex simplex method, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS ‘05, 2005, pp. 349-356, https://doi.org/10.1109/SFCS.2005.44. |
| [34] | O. Devillers, M. Glisse, X. Goaoc, and R. Thomasse, On the Smoothed Complexity of Convex Hulls, in Proceedings of the 31st International Symposium on Computational Geometry, Lipics, 2015. · Zbl 1378.68170 |
| [35] | O. Devillers, M. Glisse, X. Goaoc, and R. Thomasse, Smoothed complexity of convex hulls by witnesses and collectors, J. Comput. Geom., 7 (2016), pp. 101-144. · Zbl 1405.68410 |
| [36] | R. Dial, F. Glover, D. Karney, and D. Klingman, A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees, Networks, 9 (1979), pp. 215-248. · Zbl 0414.68035 |
| [37] | M. Dyer and A. Frieze, Random walks, totally unimodular matrices, and a randomised dual simplex algorithm, Math. Program., 64 (1994), pp. 1-16. · Zbl 0820.90066 |
| [38] | F. Eisenbrand and S. Vempala, Geometric random edge, Math. Program., 164 (2017), pp. 325-339. · Zbl 1373.90071 |
| [39] | M. Englert, H. Röglin, and B. Vöcking, Worst case and probabilistic analysis of the \(2\)-opt algorithm for the TSP, Algorithmica, 68 (2014), pp. 190-264, https://doi.org/10.1007/s00453-013-9801-4. · Zbl 1358.68131 |
| [40] | K. Fang, S. Kotz, and K. Ng, Symmetric Multivariate and Related Distributions, Monogr. Statist. Appl. Probab., Springer, New York, 1990. · Zbl 0699.62048 |
| [41] | J. J. Forrest and D. Goldfarb, Steepest-edge simplex algorithms for linear programming, Math. Program., 57 (1992), pp. 341-374, https://doi.org/10.1007/BF01581089. · Zbl 0787.90047 |
| [42] | O. Friedmann, A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games, in Proceedings of 15th International Conference on Integer Programming and Combinatorial Optimization, O. Günlük and G. J. Woeginger, eds., IPCO ‘11, Springer, New York, 2011, pp. 192-206, https://doi.org/10.1007/978-3-642-20807-2_16. · Zbl 1341.90143 |
| [43] | O. Friedmann, T. D. Hansen, and U. Zwick, Subexponential lower bounds for randomized pivoting rules for the simplex algorithm, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC ‘11, New York, 2011, ACM, pp. 283-292, https://doi.org/10.1145/1993636.1993675. · Zbl 1288.68090 |
| [44] | S. Gass and T. Saaty, The computational algorithm for the parametric objective function, Naval Res. Logist. Quart., 2 (1955), pp. 39-45, https://doi.org/10.1002/nav.3800020106. |
| [45] | A. V. Goldberg, M. D. Grigoriadis, and R. E. Tarjan, Use of dynamic trees in a network simplex algorithm for the maximum flow problem, Math. Program., 50 (1991), pp. 277-290, https://doi.org/10.1007/BF01594940. · Zbl 0743.90107 |
| [46] | D. Goldfarb, Using the steepest-edge simplex algorithm to solve sparse linear programs, Sparse Matrix Comput., 1976, pp. 227-240. · Zbl 0345.65033 |
| [47] | D. Goldfarb, Worst Case Complexity of the Shadow Vertex Simplex Algorithm, Technical report, Columbia University, New York, 1983. |
| [48] | D. Goldfarb and J. Hao, A primal simplex algorithm that solves the maximum flow problem in at most \(nm\) pivots and \(O(n^2m)\) time, Math. Program., 47 (1990), pp. 353-365. · Zbl 0713.90028 |
| [49] | D. Goldfarb and J. Hao, Polynomial-time primal simplex algorithms for the minimum cost network flow problem, Algorithmica J. IFAC, 8 (1992), pp. 145-160, https://doi.org/10.1007/BF01758840. · Zbl 0761.90037 |
| [50] | D. Goldfarb, J. Hao, and S.-R. Kai, Efficient shortest path simplex algorithms, Oper. Res., 38 (1990), pp. 624-628, https://doi.org/10.1287/opre.38.4.624. · Zbl 0723.90083 |
| [51] | D. Goldfarb and W. Y. Sit, Worst case behavior of the steepest edge simplex method, Discrete Appl. Math., 1 (1979), pp. 277-285, https://doi.org/10.1016/0166-218X(79)90004-0. · Zbl 0423.90044 |
| [52] | M. Haimovich, The Simplex Method is Very Good! On the Expected Number of Pivot Steps and Related Properties of Random Linear Programs, Technical report, Columbia University, New York, 1983. |
| [53] | T. D. Hansen and U. Zwick, An improved version of the random-facet pivoting rule for the simplex algorithm, in Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC ‘15, ACM, New York, 2015, pp. 209-218, https://doi.org/10.1145/2746539.2746557. · Zbl 1321.90080 |
| [54] | G. Höfner, Lineare Optimierung mit dem Schatteneckenalgorithmus: Untersuchungen zum mittleren Rechenaufwand und Entartungsverhalten, Ph.D. thesis, Universität Augsburg, 1995. · Zbl 0837.90084 |
| [55] | S. Huiberts, How Large is the Shadow? Smoothed Analysis of the Simplex Method, Master’s thesis, Utrecht University, Utrecht, the Netherlands, 2018, https://dspace.library.uu.nl/handle/1874/359199. · Zbl 1427.90199 |
| [56] | M. S. Hung, A polynomial simplex method for the assignment problem, Oper. Res., 31 (1983), pp. 595-600, https://doi.org/10.1287/opre.31.3.595. · Zbl 0519.90056 |
| [57] | R. G. Jeroslow, The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Math., 4 (1973), pp. 367-377, https://doi.org/10.1016/0012-365X(73)90171-4. · Zbl 0254.90027 |
| [58] | G. Kalai, A subexponential randomized simplex algorithm (extended abstract), in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC ‘92, ACM, New York, 1992, pp. 475-482, https://doi.org/10.1145/129712.129759. |
| [59] | G. Kalai and D. J. Kleitman, A quasi-polynomial bound for the diameter of graphs of polyhedra, Bull. Amer. Math. Soc. (N.S.), 26 (1992), pp. 315-316, https://doi.org/10.1090/S0273-0979-1992-00285-9. · Zbl 0751.52006 |
| [60] | N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), pp. 373-395, https://doi.org/10.1007/BF02579150. · Zbl 0557.90065 |
| [61] | J. A. Kelner and D. A. Spielman, A randomized polynomial-time simplex algorithm for linear programming, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC ‘06, ACM, New York, 2006, pp. 51-60, https://doi.org/10.1145/1132516.1132524. · Zbl 1301.68262 |
| [62] | L. G. Khachiyan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR, 244 (1979), pp. 1093-1096. · Zbl 0414.90086 |
| [63] | V. Klee and G. J. Minty, How Good is the Simplex Algorithm, Technical report, University of Washington, 1970. · Zbl 0297.90047 |
| [64] | D. G. Larman, Paths of polytopes, Proc. Lond. Math. Soc. (3), 20 (1970), pp. 161-178. · Zbl 0199.59301 |
| [65] | Y. T. Lee and A. Sidford, Path finding methods for linear programming: Solving linear programs in \(\sqrt{rank}\) iterations and faster algorithms for maximum flow, in Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS ‘14, 2014, pp. 424-433, https://doi.org/10.1109/FOCS.2014.52. |
| [66] | C. E. Lemke, Bimatrix equilibrium points and mathematical programming, Manag. Sci., 11 (1965), pp. 681-689. · Zbl 0139.13103 |
| [67] | J. Matoušek, Lectures on Discrete Geometry, Grad. Texts in Math. 212, Springer, New York, 2002. · Zbl 0999.52006 |
| [68] | J. Matoušek, M. Sharir, and E. Welzl, A subexponential bound for linear programming, Algorithmica J. IFAC, 16 (1996), pp. 498-516, https://doi.org/10.1007/s004539900062. · Zbl 0857.68119 |
| [69] | B. Matschke, F. Santos, and C. Weibel, The width of five-dimensional prismatoids, Proc. Lond. Math. Soc. (3), 110 (2015), pp. 647-672, https://doi.org/10.1112/plms/pdu064. · Zbl 1330.52015 |
| [70] | N. Megiddo, A note on the generality of the self-dual algorithm with various starting points, Methods Oper. Res., 49 (1985), pp. 271-275. · Zbl 0561.90063 |
| [71] | N. Megiddo, Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm, Math. Program., 35 (1986), pp. 140-172, https://doi.org/10.1007/BF01580645. · Zbl 0618.90061 |
| [72] | S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2 (1992), pp. 575-601, https://doi.org/10.1137/0802028. · Zbl 0773.90047 |
| [73] | K. G. Murty, Computational complexity of parametric linear programming, Math. Program., 19 (1980), pp. 213-219, https://doi.org/10.1007/BF01581642. · Zbl 0443.90102 |
| [74] | D. Naddef, The Hirsch conjecture is true for (0,1)-polytopes, Math. Program., 45 (1989), pp. 109-110, https://doi.org/10.1007/BF01589099. · Zbl 0684.90071 |
| [75] | J. B. Orlin, Genuinely Polynomial Simplex and Non-Simplex Algorithms for the Minimum Cost Flow Problem, Technical report, MIT Press, Cambridge, MA, 1984. |
| [76] | J. B. Orlin, S. A. Plotkin, and E. Tardos, Polynomial dual network simplex algorithms, Math. Program., 60 (1993), pp. 255-276, https://doi.org/10.1007/BF01580615. · Zbl 0784.90097 |
| [77] | I. Post and Y. Ye, The simplex method is strongly polynomial for deterministic Markov decision processes, Math. Oper. Res., 40 (2015), pp. 859-868. · Zbl 1329.90084 |
| [78] | J. Renegar, A polynomial-time algorithm, based on Newton’s method, for linear programming, Math. Program., 40 (1988), pp. 59-93, https://doi.org/10.1007/BF01580724. · Zbl 0654.90050 |
| [79] | A. Sankar, D. A. Spielman, and S.-H. Teng, Smoothed analysis of the condition numbers and growth factors of matrices, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 446-476, https://doi.org/10.1137/S0895479803436202. · Zbl 1179.65033 |
| [80] | F. Santos, A counterexample to the Hirsch conjecture, Ann. of Math. (2), 176 (2012), pp. 383-412, https://doi.org/10.4007/annals.2012.176.1.7. · Zbl 1252.52007 |
| [81] | E. Schnalzger, Lineare Optimierung mit dem Schatteneckenalgorithmus im Kontext probabilistischer Analysen, Ph.D. thesis, Universität Augsburg, 2014. · Zbl 1311.90073 |
| [82] | R. Shamir, The efficiency of the simplex method: A survey, Manag. Sci., 33 (1987), pp. 301-334, https://doi.org/10.1287/mnsc.33.3.301. · Zbl 0612.90081 |
| [83] | S. Smale, On the average number of steps of the simplex method of linear programming, Math. Program., 27 (1983), pp. 241-262. · Zbl 0526.90060 |
| [84] | D. A. Spielman and S.-H. Teng, Smoothed analysis of termination of linear programming algorithms, Math. Program., 97 (2003), pp. 375-404, https://doi.org/10.1007/s10107-003-0448-9. · Zbl 1035.90042 |
| [85] | D. A. Spielman and S.-H. Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, J. ACM, 51 (2004), pp. 385-463, https://doi.org/10.1145/990308.990310. · Zbl 1192.90120 |
| [86] | N. Sukegawa, An asymptotically improved upper bound on the diameter of polyhedra, Discrete Comput. Geom., 62 (2019), pp. 690-699, https://doi.org/10.1007/s00454-018-0016-y. · Zbl 1423.52018 |
| [87] | M. J. Todd, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems, Math. Program., 35 (1986), pp. 173-192. · Zbl 0613.90094 |
| [88] | M. J. Todd, An improved Kalai-Kleitman bound for the diameter of a polyhedron, SIAM J. Discrete Math., 28 (2014), pp. 1944-1947. · Zbl 1316.52021 |
| [89] | R. Vershynin, Beyond Hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method, SIAM J. Comput., 39 (2009), pp. 646-678, https://doi.org/10.1137/070683386. · Zbl 1200.68128 |
| [90] | Y. Ye, The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate, Math. Oper. Res., 36 (2011), pp. 593-603. · Zbl 1245.90140 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
