On the Expected Condition Number of Linear Programming Problems

Let A be an n × m real matrix and consider the linear conic system Ax ≤ 0, x ≠ 0. In [Cheung and Cucker 2001] a condition number script C sign(A) for this system is defined. In this paper we let the coefficients of A be independent identically distributed random variables with standard Gaussian distribution and we estimate the moments of the random variable ln script C sign(A). In particular, when n is sufficiently larger than m we obtain for its expected value E(ln script C sign(A)) = max{ln m, ln ln n} + script O sign(1). Bounds for the expected value of the condition number introduced by Renegar [1994b, 1995a, 1995b] follow.