Conditioning of convex programs from a primal-dual perspective

• 成果类型: Article
• 署名作者: Peña, J
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.26.2.206.10551
• 发表日期: 2001
• 页码: 206-220
• 关键词: interior-point methods; Complexity theory; ill-posedness

摘要

Given a convex program and its dual, we analyze the conditioning of the primal-dual system of constraints, obtained by putting the primal and dual constraints together. We show that the conditioning of the primal-dual system can be estimated in terms of the conditioning of the primal and dual systems. In particular, provided both the primal and dual systems are well-conditioned. the primal-dual system is well-conditioned. We also investigate how the conditioning of the primal-dual system relates to properties of both the primal and dual problems, providing in this way a primal-dual viewpoint for the theory of condition numbers for convex programming.