Is $g(x_1, x_2) = (\alpha – x_1)^2 + (\max \{\alpha, x_1\} + \beta – x_2)^2$ convex

Question

Let $\alpha \geq 0$ and $\beta \geq 0$. Can we prove or disprove the following function is convex on $x_2 \geq x_1 \geq 0$?
$$
g(x_1, x_2) = (\alpha – x_1)^2 + (\max \{\alpha, x_1\} + \beta – x_2)^2
$$

My Approach: It is clear that the function $\max \{\alpha, x_1\} – x_2$ is convex. For $x \geq 0$, $x^2$ is convex and increasing, so composition of these two functions is convex. But this does not seem to work in general because of the region that $\max \{\alpha, x_1\} – x_2$ might go negative.

Answer 1

As you already pointed out, $(\max \{\alpha, x_1\} + \beta - x_2)^2$ might descrease as $x_1$ increases when $x_1 + \beta - x_2 < 0$. So, to show a function is non-convex, one only needs to find a counter example.

Try the following three points (find a large enough $n > 2$ so that $\alpha - \frac{1}{n}\beta > 0$, and let $\lambda=\frac{1}{2}$).

• $g(\alpha - \frac{1}{n}\beta, \alpha + 2\beta) = \frac{\beta^2}{n^2} + \beta^2 = \frac{n^2+1}{n^2}\beta^2;$
• $g(\alpha, \alpha + 2\beta) = \beta^2;$
• $g(\alpha + \frac{1}{n}\beta, \alpha + 2\beta) = \frac{\beta^2}{n^2} + \frac{{(n-1)}^2\beta^2}{n^2} = \frac{{(n-1)}^2 + 1}{n^2}\beta^2.$

Now $\frac{g(\alpha - \frac{1}{n}\beta, \alpha + 2\beta) + g(\alpha + \frac{1}{n}\beta, \alpha + 2\beta)}{2}=\frac{n^2+{(n-1)}^2+2}{2n^2}\beta^2<\beta^2=g(\alpha, \alpha + 2\beta)\\ =g(\frac{\left(\alpha - \frac{1}{n}\beta\right) + \left(\alpha + \frac{1}{n}\beta\right)}{2}, \frac{(\alpha + 2\beta) + (\alpha + 2\beta)}{2}).$

Hence the function is not convex.