Abstract
We perform a smoothed analysis of the GCC-condition number \({\fancyscript{C}(A)}\) of the linear programming feasibility problem \({\exists x\in\mathbb{R}^{m+1}\,Ax < 0}\). Suppose that \({\bar{A}}\) is any matrix with rows \({\overline{a}_i}\) of euclidean norm 1 and, independently for all i, let a i be a random perturbation of \({\overline{a}_i}\) following the uniform distribution in the spherical disk in S m of angular radius arcsin σ and centered at \({\overline{a}_i}\). We prove that \({\mathbb{E}({\rm ln}\,\fancyscript{C}(A)) =\mathcal{O} (mn/\sigma)}\). A similar result was shown for Renegar’s condition number and Gaussian perturbations by Dunagan et al. (Math Program Ser A, 2009). Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius arcsin σ, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of Bürgisser et al. (Math Comp 77(263), 2008) with techniques of Dunagan et al.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Allendoerfer C.B.: Steiner’s formulae on a general S n+1. Bull. Amer. Math. Soc. 54, 128–135 (1948)
Ball K.: The reverse isoperimetric problem for Gaussian measure. Discret. Comput. Geom. 10(4), 411–420 (1993)
Bonnesen, T., Fenchel, W.: Theorie der konvexen Körper. Springer, Berlin, Berichtigter Reprint (1974)
Bürgisser, P.: Smoothed analysis of condition numbers. In: Foundations of Computational Mathematics, Hong Kong 2008, pp. 1–41. Cambridge University Press, Cambridge (2009)
Bürgisser P., Cucker F., Lotz M.: Coverage processes on spheres and condition numbers for linear programming. Ann. Probab. 38(2), 570–604 (2010)
Bürgisser P., Cucker F., Lotz M.: Smoothed analysis of complex conic condition numbers. J. Math. Pures et Appl. 86, 293–309 (2006)
Bürgisser P., Cucker F., Lotz M.: The probability that a slightly perturbed numerical analysis problem is difficult. Math. Comput. 77(263), 1559–1583 (2008)
Cheung D., Cucker F.: A new condition number for linear programming. Math. Program. 91(1, Ser. A), 163–174 (2001)
Cheung D., Cucker F.: Probabilistic analysis of condition numbers for linear programming. J. Optim. Theor. Appl. 114, 55–67 (2002)
Cheung D., Cucker F., Hauser R.: Tail decay and moment estimates of a condition number for random linear conic systems. SIAM J. Optim. 15(4), 1237–1261 (2005) (electronic)
Cucker, F., Hauser, R., Lotz, M.: Adversarial smoothed analysis. To appear in J. Complexity
Cucker, F., Peña, J.: A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine. SIAM J. Optim. 12(2), 522–554 (electronic) (2001/02)
Cucker F., Wschebor M.: On the expected condition number of linear programming problems. Numer. Math. 94, 419–478 (2002)
Demmel J.: The probability that a numerical analysis problem is difficult. Math. Comput. 50, 449–480 (1988)
Dunagan, J., Spielman, D.A., Teng, S.-H.: Smoothed analysis of condition numbers and complexity implications for linear programming. Math. Program. Ser. A (2009). doi:10.1007/s10107-009-0278-5
Glasauer, S.: Integralgeometrie konvexer Körper im sphärischen Raum. PhD thesis, Universität Freiburg im Br. (1995)
Goffin J.-L.: The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5(3), 388–414 (1980)
Hauser R., Müller T.: Conditioning of random conic systems under a general family of input distributions. Found. Comput. Math. 9(3), 335–358 (2009)
Howard R.: The kinematic formula in Riemannian homogeneous spaces. Mem. Amer. Math. Soc. 106(509), vi+69 (1993)
Renegar J.: Some perturbation theory for linear programming. Math. Program. 65(1, Ser. A), 73–91 (1994)
Renegar J.: Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5(3), 506–524 (1995)
Renegar J.: Linear programming, complexity theory and elementary functional analysis. Math. Program. 70(3, Ser. A), 279–351 (1995)
Sankar A., Spielman D.A., Teng S.H.: Smoothed analysis of the condition numbers and growth factors of matrices. SIAM J. Matrix Anal. Appl. 28(2), 446–476 (2006) (electronic)
Schneider R.: Smooth approximation of convex bodies. Rend. Circ. Mat. Palermo (2) 33(3), 436–440 (1984)
Smale S.: Complexity theory and numerical analysis. In: Iserles, A. (eds) Acta Numerica, pp. 523–551. Cambridge University Press, Cambridge (1997)
Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms. In: Proceedings of the International Congress of Mathematicians, vol. I, pp. 597–606 (2002)
Spielman D.A., Teng S.-H.: Smoothed analysis of termination of linear programming algorithms. Math. Programm. Series B 97, 375–404 (2003)
Spielman D.A., Teng S.-H.: Smoothed analysis: Why the simplex algorithm usually takes polynomial time. J. ACM 51, 385–463 (2004)
Spivak M.: A comprehensive introduction to differential geometry, Vol III. 2nd edn. Publish or Perish Inc, Wilmington, Del (1979)
Webster R.: Convexity. Oxford Science Publications. The Clarendon Press Oxford University Press, New York (1994)
Wendel J.G.: A problem in geometric probability. Math. Scand. 11, 109–111 (1962)
Weyl H.: On the volume of tubes. Am. J. Math. 61(2), 461–472 (1939)
Author information
Authors and Affiliations
Corresponding author
Additional information
P. Bürgisser and D. Amelunxen are partially supported by DFG grant BU 1371/2-1 and DFG Research Training Group on Scientific Computation GRK 693 (PaSCo GK).
Rights and permissions
About this article
Cite this article
Bürgisser, P., Amelunxen, D. Robust smoothed analysis of a condition number for linear programming. Math. Program. 131, 221–251 (2012). https://doi.org/10.1007/s10107-010-0346-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-010-0346-x