×

Coverage processes on spheres and condition numbers for linear programming. (English) Zbl 1205.60027

Let \(p(n,m,\alpha)\) be the probability that \(n\) spherical caps of angular radius \(\alpha\) do not cover the whole sphere \(S^m\). The authors give an exact formula for this probability in the case \(\alpha\in[\pi/2,\pi]\) and an upper bound in the case \(\alpha\in[0,\pi/2]\), which tends to the exact value as \(\alpha\to\pi/2\). The obtained upper bound yields upper bounds for the expected number of caps that are needed to cover the whole sphere.
Then the authors study the condition number \(\mathcal{C}(A)\) of the linear programming feasibility problem concerning the existence of a nonzero \(x\in\mathbb{R}^{m+1}\) such that \(Ax\leq 0\) componentwise, where a \(n\times(m+1)\) matrix \(A\) is randomly chosen according to the standard normal distribution. The relation to spherical caps is explained by the fact that \(\mathcal{C}(A)\) equals \(1/|\cos\rho(A)|\), where \(\rho(A)\) is the radius of a largest excluding cap for \(A=(a_1,\dots,a_n)\), i.e. the complement to the smallest cap that contains the points \(a_1,\dots,a_n\). The authors exactly determine the distribution of \(\mathcal{C}(A)\) conditioned on \(A\) being feasible and provide an upper bound on the distribution function in the infeasible case. From these results they show that \[ \mathbf{E} \ln\mathcal{C}(A)\leq 2 \ln(m+1)+3.31\,,\quad n>m\,, \] which is the sharpest known bound for this expectation.

MSC:

60D05 Geometric probability and stochastic geometry
52A22 Random convex sets and integral geometry (aspects of convex geometry)
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Agmon, S. (1954). The relaxation method for linear inequalities. Canad. J. Math. 6 382-392. · Zbl 0055.35001
[2] Bürgisser, P. and Amelunxen, D. (2008). Uniform smoothed analysis of a condition number for linear programming. Accepted for Math. Program. A. Available at · Zbl 1242.90098
[3] Cheung, D. and Cucker, F. (2001). A new condition number for linear programming. Math. Program. 91 163-174. · Zbl 1072.90564
[4] Cheung, D. and Cucker, F. (2002). Probabilistic analysis of condition numbers for linear programming. J. Optim. Theory Appl. 114 55-67. · Zbl 1041.90028
[5] Cheung, D., Cucker, F. and Hauser, R. (2005). Tail decay and moment estimates of a condition number for random linear conic systems. SIAM J. Optim. 15 1237-1261. · Zbl 1097.90057
[6] Cucker, F. and Peña, J. (2002). A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine. SIAM J. Optim. 12 522-554. · Zbl 0996.90052
[7] Cucker, F. and Wschebor, M. (2002). On the expected condition number of linear programming problems. Numer. Math. 94 419-478. · Zbl 1030.65039
[8] Dunagan, J., Spielman, D. A. and Teng, S.-H. (2009). Smoothed analysis of condition numbers and complexity implications for linear programming. Math. Programming . To appear. Available at http://arxiv.org/abs/cs/0302011v2. · Zbl 1218.90109
[9] Dvoretzky, A. (1956). On covering a circle by randomly placed arcs. Proc. Natl. Acad. Sci. USA 42 199-203. JSTOR: · Zbl 0074.12301
[10] Gilbert, E. N. (1965). The probability of covering a sphere with N circular caps. Biometrika 52 323-330. JSTOR: · Zbl 0137.36202
[11] Goffin, J.-L. (1980). The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5 388-414. JSTOR: · Zbl 0442.90051
[12] Hall, P. (1985). On the coverage of k -dimensional space by k -dimensional spheres. Ann. Probab. 13 991-1002. · Zbl 0582.60015
[13] Hall, P. (1988). Introduction to the Theory of Coverage Processes . Wiley, New York. · Zbl 0659.60024
[14] Hauser, R. and Müller, T. (2009). Conditioning of random conic systems under a general family of input distributions. Found. Comput. Math. 9 335-358. · Zbl 1193.90199
[15] Janson, S. (1986). Random coverings in several dimensions. Acta Math. 156 83-118. · Zbl 0597.60014
[16] Kahane, J.-P. (1959). Sur le recouvrement d’un cercle par des arcs disposés au hasard. C. R. Math. Acad. Sci. Paris 248 184-186. · Zbl 0090.35801
[17] Miles, R. E. (1968). Random caps on a sphere. Ann. Math. Statist. 39 1371. · Zbl 0165.58001
[18] Miles, R. E. (1969). The asymptotic values of certain coverage probabilities. Biometrika 56 661-680. JSTOR: · Zbl 0184.41501
[19] Miles, R. E. (1971). Isotropic random simplices. Adv. in Appl. Probab. 3 353-382. JSTOR: · Zbl 0237.60006
[20] Moran, P. A. P. and Fazekas de St. Groth, S. (1962). Random circles on a sphere. Biometrika 49 389-396. JSTOR: · Zbl 0108.31602
[21] Motzkin, T. S. and Schoenberg, I. J. (1954). The relaxation method for linear inequalities. Canad. J. Math. 6 393-404. · Zbl 0055.35002
[22] Reitzner, M. (2002). Random points on the boundary of smooth convex bodies. Trans. Amer. Math. Soc. 354 2243-2278. JSTOR: · Zbl 0993.60012
[23] Rosenblatt, F. (1962). Principles of Neurodynamics. Perceptrons and the Theory of Brain Mechanisms . Spartan Books, Washington, DC. · Zbl 0143.43504
[24] Santaló, L. A. (1976). Integral Geometry and Geometric Probability . Addison-Wesley, Reading, MA. · Zbl 0342.53049
[25] Siegel, A. F. (1979). Asymptotic coverage distributions on the circle. Ann. Probab. 7 651-661. · Zbl 0412.60014
[26] Siegel, A. F. and Holst, L. (1982). Covering the circle with random arcs of random sizes. J. Appl. Probab. 19 373-381. JSTOR: · Zbl 0489.60017
[27] Solomon, H. (1978). Geometric Probability . SIAM, Philadelphia, PA. · Zbl 0382.60016
[28] Stevens, W. L. (1939). Solution to a geometrical problem in probability. Ann. Eugenics 9 315-320. · Zbl 0023.05603
[29] Wendel, J. G. (1962). A problem in geometric probability. Math. Scand. 11 109-111. · Zbl 0108.31603
[30] Whitworth, W. A. (1965). DCC Exercises in Choice and Chance . Dover, New York. · JFM 28.0212.14
[31] Zähle, M. (1990). A kinematic formula and moment measures of random sets. Math. Nachr. 149 325-340. · Zbl 0725.60014
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.