On the Expected Condition Number of Linear Programming Problems
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 419-478 |
| Journal / Publication | Numerische Mathematik |
| Volume | 94 |
| Issue number | 3 |
| Publication status | Published - May 2003 |
Link(s)
Abstract
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.
Citation Format(s)
On the Expected Condition Number of Linear Programming Problems. / Cucker, Felipe; Wschebor, Mario.
In: Numerische Mathematik, Vol. 94, No. 3, 05.2003, p. 419-478.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
