Unifying Condition Numbers for Linear Programming

Dennis Cheung (50003110plink.cityu.edu.hk)
Felipe Cucker (macuckermath.cityu.edu.hk)
Javier Pena (jfpandrew.cmu.edu)

Abstract: In recent years, several condition numbers were defined for a variety of linear programming problems based upon relative distances to ill-posedness. In this paper we provide a unifying view of these condition numbers. To do so, we introduce yet another linear programming problem and show that its distance to ill-posedness naturally captures the most commonly used distances to ill-posedness.

Keywords: condition numbers, data perturbations, distance to ill-posedness

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Mathematics of Operations Research 28 (2003) 609--624.

Download:

Entry Submitted: 07/29/2002
Entry Accepted: 07/29/2002
Entry Last Modified: 11/01/2003

Modify/Update this entry