Problem Geometry and Problem Robustness in Convex Optimization

Abstract

The geometry of a set has been shown to explain complexity
properties of some convex optimization algorithms and other measures like condition numbers have similar properties. But condition numbers for optimization also affect sensitivity
of optimal solutions with respect to changes in the data, so It is a
relevant question whether the geometry of the feasible set also affect
sensitivity of solutions.
In this work we study some
of those connections and address its potential implications for
the computation of robust solutions. Robust solutions are
protected from data variation, but the change in the robust
solution with respect to nominal solutions is related to the
robustness and well posedness of the problem itself. We show how
some geometric measures of the feasible set could be used as a way of measuring this
robustness and how to estimate them.