I disagree with your second attempt, I don't understand it completely though, it's a bit ambiguous what you're saying, but the way I interpret it sounds wrong, but your first attempt is definitely wrong, you have to show that inequality holds for the coordinates of all vectors that lie in the line segment between each two vectors in the set.
Suppose that for some arbitrarily chosen $0\leq \alpha \leq 1$ we write:
$(z_1,z_2)=\alpha (x_1,x_2) + (1-\alpha) (y_1,y_2)$
Does $z_1 \cdot z_2 \geq k$ hold?
Remember that $x_1x_2 \geq k$ and $y_1y_2\geq k$.
Addendum:
This is how I can prove what you want, I don't use $\displaystyle \frac{a}{b} + \frac{b}{a} \geq 2$ in my proof, but since I'm using AM-GM inequality, I guess that with a suitable change of variables you might find a way to write what you want by using that particular inequality (which is implied by AM-GM):
As you said, we have:
$z_1 = \alpha x_1 + (1-\alpha)y_1$
$z_2 = \alpha x_2 + (1-\alpha)y_2$
Just by doing some simple algebraic manipulations, we get:
$z_1 z_2 = \alpha^2 x_1x_2 + \alpha(1-\alpha)x_1y_2 + \alpha(1-\alpha)x_2y_1 + (1-\alpha)^2y_1y_2$
Now use your hypotheses to get:
$z_1z_2 \geq \alpha^2 k + \alpha(1-\alpha)(x_1y_2+x_2y_1) +(1-\alpha)^2k$
But by using AM-GM inequality we have:
$x_1y_2+x_2y_1 \geq 2 \sqrt{x_1x_2}\sqrt{y_1y_2}\geq 2k$
Therefore, we get:
$$z_1z_2 \geq \alpha^2k + \alpha(1-\alpha)(2k)+(1-\alpha)^2k \geq k (\alpha^2+2\alpha(1-\alpha)+(1-\alpha)^2)$$
$$z_1z_2 \geq k (\alpha + (1-\alpha))^2=k$$
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.
Best Answer
I deleted my previous solution since it is complicated. I give another solution here.
Proof: We have (cf. @user125932's answer) \begin{align} g(x_1, x_2) = \left\{\begin{array}{ll} -x_1 - x_2 + 2\alpha + \beta & x_1 \le \alpha, x_2 \le \alpha + \beta \\ -x_1 + x_2 - \beta & x_1 \le \alpha, x_2 > \alpha + \beta\\ 2x_1 - x_2 - \alpha + \beta & x_1 > \alpha, x_2 \le x_1 + \beta \\ x_2 - \alpha - \beta & x_1 > \alpha, x_2 > x_1 + \beta. \end{array} \right. \end{align} It is easy to verify that $$g(x_1, x_2) = \max \{-x_1 - x_2 + 2\alpha + \beta, \ -x_1 + x_2 - \beta, \ 2x_1 - x_2 - \alpha + \beta, \ x_2 - \alpha - \beta\}.$$ Thus, $g(x_1, x_2)$ is convex (see Example 3.5, page 80, in [1]).
[1] Boyd and Vandenberghe, "Convex optimization". http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf