2

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.

Mehdi Jafarnia Jahromi
  • 1,718
  • Here is how I would prove it. A function is convex if and only if it is convex along all lines (for an example, see the proof of concavity of log-determinant in the book by Boyd and Vandenberghe). A differentiable function of one variable is convex if and only if its derivative is monotonically non-decreasing. – LinAlg Oct 25 '19 at 12:37

1 Answers1

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.

Xiaohai Zhang
  • 2,017
  • 6
  • 7
  • Thanks Xiaohai, that's a very nice counterexample. What do you think about the case that $\alpha, \beta$ are positive random variables and $g(x_1, x_2) = \mathbb{E}[\cdots]$? Is there any distribution that gives convex $g$? – Mehdi Jafarnia Jahromi Oct 28 '19 at 02:27
  • Fixing $x_2$, ${(max{\alpha, x_1} + \beta - x_2)}^2$ has a flat region of $x_1\le\alpha$ . If $x_2 \le \alpha + \beta$, the function remains convex (rise after the flat region); otherwise, a valley follows the flat region, and it is NOT convex. So if x_2 distributes in $[0, \alpha + \beta]$, then the $\mathbb{E}$ edition can be convex. Otherwise, I do not see a way to push up "valleys" so that the $\mathbb{E}$ function is convex. – Xiaohai Zhang Oct 29 '19 at 02:46
  • @ Xiaohai What if instead of $(\cdot)^2$ for the first and second term of $g(x_1, x_2)$, we replace it with $|\cdot|$. Is it still non convex? – Mehdi Jafarnia Jahromi Nov 25 '19 at 19:25