Proving that the given function of 2 variables is convex

Question

Let $f\colon\mathbb{R}\to\mathbb{R}$ be a continuous function such that $|f|$ is convex.
Define $F\colon\mathbb{R}^2\to\mathbb{R}$ as $F(x,y)=|f(x)|+|y-f(x)|$.
Prove that $F$ is convex.

AFAIK this is an old contest problem from NA.
I have searched the Putnam archive, but didn't see it there.

My only idea was the most straightforward attempt:
we need
$F(tx_1+(1-t)x_2,\: ty_1+(1-t)y_2)
\le
tF(x_1,y_1)+(1-t)F(x_2,y_2)$
for all $t\in[0,1]$, $x_1,x_2,y_1,y_2\in\mathbb{R}$, write this in terms of $f$ and use the fact that $|f|$ is convex, but the remaining inequality turned to be false, so this is not the way.

Answer 1

Since $|f(x)|$ is convex and continuous, we can prove the convexity of two other single-variable functions: $f_+(x) = \max\{0, f(x)\}$ and $f_-(x) = \max\{-f(x), 0\}$.

This follows from the definition of convexity by casework on the signs of $f(x_1), f(x_2)$, which I will only do for $f^+$:

• If they're both $\ge 0$, then everywhere between them, $f_+$ is either equal to $|f|$ (and we are done by convexity of $|f|$) or to $0$.
• If they're both $\le 0$, then $f^+(x_1) = f^+(x_2) = 0$; we are happy unless $f(x) > 0$ for some $x \in [x_1, x_2]$. This can't happen: by IVT, we find $a \in [x_1, x]$ and $b \in [x, x_2]$ where $f(a)=f(b)=0$, and then $|f(a)| < |f(x)| > |f(b)|$ violates convexity of $|f|$.
• If $f(x_1) > 0 > f(x_2)$, then $f(x) = 0$ for some $x \in [x_1,x_2]$. We apply the previous cases to $[x_1,x]$ and $[x, x_2]$, then notice that the line segments from $(x_1, f^+(x_1))$ to $(x, f^+(x))$ to $(x_2, f^+(x_2))$ lie below the line segment directly from $(x_1, f^+(x_1))$ to $(x_2, f^+(x_2))$.
• If $f(x_1) < 0 < f(x_2)$, the argument is the same as in the previous case.

Once we have that lemma, the rest is easy: \begin{align} F(x,y) &= \max\{f(x), -f(x)\} + \max\{f(x)-y, y-f(x)\} \\ &= \max\{f(x) + f(x)-y, f(x) + y-f(x), -f(x)+f(x)-y, -f(x)+y-f(x)\} \\ &= \max\{ \max\{2f(x)-y, -y\}, \max\{y, y-2f(x)\}\} \\ &= \max\{ 2f_+(x) - y, 2f_-(x) + y)\}. \end{align} This is the max of two convex functions, which is convex.