Showing convexity of a discrete function

[TaPaKaH]

Suppose we have a function $f:\mathbb{N}\times\mathbb{N}\to\mathbb{R}_+$ that is

• increasing: $f(x+e_i)\geq f(x)$ for any $x\in\mathbb{N}^2$ and $i\in\{1,2\}$;
• convex: $f(x+2e_i)-f(x+e_i)\geq f(x+e_i)-f(x)$ for any $x\in\mathbb{N}^2$ and $i\in\{1,2\}$.

How could one show that a function $g(x):=cf(x)-\max\{c_1\left(f(x)-f(x-e_1)\right),c_2\left(f(x)-f(x-e_2)\right)\}$ for $c=\max\{c_1,c_2\}$ ($c_1,c_2\geq0$) is also convex wrt definition above?

 

[verty]

Have you tried substituting g into that convexity inequality?

 

[TaPaKaH]

So far I did case-by-case analysis branching on terms, at which maxima for $f(x+2e_i)$, $f(x+e_i)$ and $f(x)$ are achieved. Six of eight cases went rather smooth, but two cases are giving me problems.

Case 1:

\begin{cases}
c_1\left[f(x)-f(x-e_1)\right]&\geq c_2\left[f(x)-f(x-e_2)\right]\\
c_1\left[f(x+e_1)-f(x)\right]&\geq c_2\left[f(x+e_1)-f(x+e_1-e_2)\right]\\
c_1\left[f(x+2e_1)-f(x+e_1)\right]&\leq c_2\left[f(x+2e_1)-f(x+2e_1-e_2)\right],
\end{cases}
in which case
\begin{array}{rl}
g(x)&=c f(x)-c_1\left[f(x)-f(x-e_1)\right]\\
g(x+e_1)&=c f(x+e_1)-c_1\left[f(x+e_1)-f(x)\right]\\
g(x+2e_1)&=c f(x+2e_1)-c_2\left[f(x+2e_1)-f(x+2e_1-e_2)\right].
\end{array}
What we want to show is that
\begin{array}{rll}
g(x+2e_1)-2g(x+e_1)+g(x)
&=\begin{matrix}
cf(x+2e_1)-c_2\left[f(x+2e_1)-f(x+2e_1-e_2)\right]\\
-2c f(x+e_1)+2c_1\left[f(x+e_1)-f(x)\right]\\
+cf(x)-c_1\left[f(x)-f(x-e_1)\right]
\end{matrix}
&\geq0
\end{array}

Case 2:

\begin{cases}
c_1\left[f(x)-f(x-e_1)\right]&\geq c_2\left[f(x)-f(x-e_2)\right]\\
c_1\left[f(x+e_1)-f(x)\right]&\leq c_2\left[f(x+e_1)-f(x+e_1-e_2)\right]\\
c_1\left[f(x+2e_1)-f(x+e_1)\right]&\leq c_2\left[f(x+2e_1)-f(x+2e_1-e_2)\right],
\end{cases}
in which case
\begin{array}{rl}
g(x)&=c f(x)-c_1\left[f(x)-f(x-e_1)\right]\\
g(x+e_1)&=c f(x+e_1)-c_2\left[f(x+e_1)-f(x+e_1-e_2)\right]\\
g(x+2e_1)&=c f(x+2e_1)-c_2\left[f(x+2e_1)-f(x+2e_1-e_2)\right].
\end{array}
What we want to show is that
\begin{array}{rll}
g(x+2e_1)-2g(x+e_1)+g(x)
&=\begin{matrix}
cf(x+2e_1)-c_2\left[f(x+2e_1)-f(x+2e_1-e_2)\right]\\
-2c f(x+e_1)+2c_2\left[f(x+e_1)-f(x+e_1-e_2)\right]\\
+cf(x)-c_1\left[f(x)-f(x-e_1)\right]
\end{matrix}
&\geq0
\end{array}

I guess the proof lies in rearranging the terms in a smart way and then applying the assumptions and properties. One can also use that $f$ is also supermodular, that is $f(x+e_1+e_2)+f(x)\geq f(x+e_1)+f(x+e_2)$ for any $x\in\mathbb{N}^2$.