Solving linear programs with finite precision. I: Condition numbers and random programs
type: Item
instance of: scholarly article
title: Solving linear programs with finite precision. I: Condition numbers and random programs
zbMATH Open document ID: 1082.90060
author: Dennis Cheung
author: Felipe Cucker
published in: Mathematical Programming. Series A. Series B
publication date: 2004-03-11T00:00:00Z
review text: 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.
reviewed by: Peter Brucker
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 2055187
zbMATH Keywords: linear programming
zbMATH Keywords: condition number
describes a project that uses: mctoolbox
MaRDI profile type: Publication
full work available at URL: s10107-003-0393-7
OpenAlex ID: W2006494263
Wikidata QID: Q57733230
DOI: 10.1007/S10107-003-0393-7
description: scientific article; zbMATH DE number 2055187