Convex functions: bounding the difference - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:29:04Z http://mathoverflow.net/feeds/question/117062 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/117062/convex-functions-bounding-the-difference Convex functions: bounding the difference Rajhans 2012-12-23T02:20:49Z 2012-12-23T03:24:28Z <p>Suppose you are given a convex function $f: R^d \rightarrow R$. Let us say you are given $x,x' \in R^d$ and $x_1, x_2, \ldots, x_n \in R^d$ such that </p> <p>$$\sum_{i=1}^n (x_i - x') = x - x'.$$</p> <p>Is it possible to bound $f(x) - f(x')$ in terms of $f(x_i) - f(x')$? </p> <p>That is, a bound of the form</p> <p>$$f(x) - f(x') \leq \sum_{i}^n \left( f(x_i) - f(x') \right) + \sum_i^n \epsilon(x_i,x),$$</p> <p>where $\epsilon_i$ are some small "error" functions based on some property of $f$? Is there a class of functions $f$ for which this will be valid with $\epsilon = 0$?</p> http://mathoverflow.net/questions/117062/convex-functions-bounding-the-difference/117066#117066 Answer by Robert Israel for Convex functions: bounding the difference Robert Israel 2012-12-23T03:24:28Z 2012-12-23T03:24:28Z <p>$$f(x) - f(x') \le \sum_i \left(f(x_i) - f(x')\right)$$ iff the function $g(x) = f(x + x') - f(x')$ is subadditive. </p>