0

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.

Shmoopy
  • 325

1 Answers1

2

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,\ )$.

Did
  • 279,727
  • 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 09 '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 09 '13 at 14:58