Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

$$\sum_{i=1}^n (x_i - x') = x - x'.$$

Is it possible to bound $f(x) - f(x')$ in terms of $f(x_i) - f(x')$?

That is, a bound of the form

$$f(x) - f(x') \leq \sum_{i}^n \left( f(x_i) - f(x') \right) + \sum_i^n \epsilon(x_i,x),$$

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$?

share|improve this question
1  
Crossposted to math.SE: math.stackexchange.com/q/263923/264 In the future, please wait some time before posting your question in multiple fora, and when you do, provide links to the other posts - as you can imagine, it would be frustrating for someone to put time into answering your question here, only to see hear from you that you'd already gotten the solution elsewhere. –  Zev Chonoles Dec 23 '12 at 3:21
    
Sorry about this. I realized after posting to math.SE that mathoverflow might be a better place. Thanks for pointing it out. –  Rajhans Dec 24 '12 at 23:25
add comment

1 Answer 1

up vote 1 down vote accepted

$$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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.