Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have $ x_1,x_2,..,x_n\in\left[0,1\right] $.

Suppose $ x=(x_1,x_2,..,x_n), F(x,i,j,\epsilon)=g(x_1,...,x_i+\epsilon,...,x_j-\epsilon,..,x_n) $ . We know that $F$ is convex with respect to $\epsilon$. How do you show that $F(x,i,j,\epsilon)\geq F(x,i,j,0) $ for all $ \epsilon \in \left[-min\left\{ x_{i},1-x_{j}\right\} ,min\left\{ 1-x_{i},x_{j}\right\} \right] $ ?

Taken from section 2 at http://www2.warwick.ac.uk/fac/sci/dcs/people/maxim_sviridenko/dirmaxcut.pdf

Only that they said that it follows directly from $F$ being convex, but I can't figure out why.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

To abstract a little bit the situation, consider a convex function $u$ defined on some interval $[s,t]$ with $s\lt0\lt t$. Then the question is to show that $$ u(0)\leqslant\max\{u(s),u(t)\}. $$ (Note that one does not prove that $u(0)\leqslant u(s)$ and $u(0)\leqslant u(t)$, and that these inequalities have no reason to be true.)

To prove this, note that $0=\theta s+(1-\theta )t$ for some $\theta $ in $(0,1)$ hence, by convexity, one has $u(0)\leqslant \theta u(s)+(1-\theta )u(t)$. Thus, $$ u(0)\leqslant \theta \max\{u(s),u(t)\}+(1-\theta )\max\{u(s),u(t)\}=\max\{u(s),u(t)\}. $$ Finally, apply this to the function $u=F(x,i,j,\ )$.

share|improve this answer
    
They said that given the fact that it holds $\epsilon$-convexity, it holds that $ F(x,i,j,\epsilon) \geq F(x,i,j,0) $ –  Shmoopy Feb 9 '13 at 14:22
    
I see, so I've been spending the last 4 hours trying to figure out why something wrong is true. Thanks! –  Shmoopy Feb 9 '13 at 14:58

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.