Unifying condition numbers for linear programming

• 成果类型: Article
• 署名作者: Cheung, D; Cucker, F; Peña, J
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.28.4.609.20520
• 发表日期: 2003
• 页码: 609-624
• 关键词: Complexity; distance; systems; componentwise

摘要

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 soma: 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.