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

Abstract

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”. Problemgeometry 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 radiusof 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.