The Condition of a Function Relative to a Polyhedron
Date:
Locations:
- INFORMS Annual Meeting 2018, Phoenix, AZ
- ISMP 2018, Bordeaux, France
- MOPTA 2017, Bethlehem, PA
We propose a condition number of a smooth convex func- tion relative to a reference polytope. This relative condition number is defined as the ratio of a relative smooth constant to a relative strong convexity constant of the function, where both constants are relative to the reference polytope. The relative condition number extends the main properties of the traditional condition number. In particular, we show that the condition number of a quadratic convex function relative to a polytope is precisely the square of the diameter-to-facial- distance ratio of a scaled polytope for a canonical scaling induced by the function. Furthermore, we illustrate how the relative condition number of a function bounds the linear rate of convergence of first-order methods for minimization of the function over the polytope.