On the Expected Condition Number of Linear Programming Problems

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

19 Scopus Citations
View graph of relations

Author(s)

  • Felipe Cucker
  • Mario Wschebor

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.

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 ReviewsRGC 21 - Publication in refereed journalpeer-review