Solving linear programs with finite precision. I: Condition numbers and random programs (Q1424293)

Let \(d= (A,b,c)\) be a representation of the linear program \[ P_d: \min C^t x\quad\text{s.t. }Ax= b;\quad x\geq 0 \] and let \(\| d\|\) be the operator norm corresponding with the matrix \[ M_d= \begin{pmatrix} A & b\\ c^T & 0.\end{pmatrix} \] \(d\) is called feasible well-posed if the corresponding linear program \(P_d\) has a unique optimal basis \(B\). In this case the distance \(\rho(d)\) to ill-posedness is defined by the minimum of all values \(\|\vartheta d\|\) with the property that \(B\) is not an optimal basis for the linear program \(P_{d+\vartheta d}\). If \(d\) is not feasible well-posed one defines \(\rho(d)= 0\). The condition number of \(d\) is given by \[ {\mathcal K}(d)= {\| d\|\over\rho(d)}. \] Two characterizations of \({\mathcal K}(d)\) via distances to degenerary and singularity are given. Also bounds for the expected value, as well as for higher moments, of \(\log{\mathcal K}(d)\) when the entries \(A\), \(b\), and \(c\) are i.i.d. random variables with normal distribution are derived.