Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization

• 成果类型: Article
• 署名作者: Vera, Jorge R.
• 署名单位: Pontificia Universidad Catolica de Chile
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0709-1
• 发表日期: 2014
• 页码: 47-79
• 关键词: condition number; complexity; constraints

摘要

The effect of data perturbation and uncertainty has always been an important consideration in Optimization. It is important to know whether a given problem is very sensible to perturbations on the data or, on the contrary, is more robust. Problem geometry does have an impact on the sensitivity of the problem and in this paper we analyze this connection by developing bounds to the change in the optimal value of a conic linear problem in terms of some geometric measures related to the radius of inscribed and circumscribed balls to the feasible region of the problem. We also present a parametric analysis for Linear Programming which allows us to construct an estimate of safety limits for perturbations of the data. These results are developed in relation to questions in robust optimization.