On the Expected Condition Number of Linear Programming Problems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

19 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)419-478
Journal / PublicationNumerische Mathematik
Volume94
Issue number3
Publication statusPublished - May 2003

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.