I'm spending a lot of time proving the following function convex. It should be trivial.. would love to have someone point out the obvious.
We have the piecewise function $$f(x)=\begin{cases}
x^2 & \text{if } x \leq 0 \\
0 & \text{otherwise}
\end{cases}$$
For $f(x)$ to be convex, we need to prove:
$$
\lambda f(x_1) + (1-\lambda)f(x_2) \leq f(\lambda x_1 + (1-\lambda)x_2), \forall x_1, x_2 \in \mathbb{R}, \forall \lambda \in [0,1]
$$
- For $x_1, x2 \leq 0$, we know that the inequality holds, as $f(x)=x^2$ has second derivative 2 for all x, which is sufficient to prove it is convex, and thus satisfy the inequality.
- If $x_1, x_2 \geq 0$, by a similar argument, the second derivative is 0, and thus it satisfies the inequality.
- The problem comes when I try to prove the inequality to be true for $x_1 \leq 0$ and $x_2 \geq 0$.
- On LHS, substituting the function into the inequality:
$$
\text{LHS} = \lambda f(x_1) + (1-\lambda)f(x_2) \\
$$ - Since $x_2 \geq 0$, we know that $f(x_2) = 0$, thus:
$$
\text{LHS} = \lambda f(x_1) = \lambda x_1^2
$$ - On RHS, we have:
$$f(\lambda x_1+(1-\lambda)x_2)=\begin{cases}
(\lambda x_1+(1-\lambda)x_2)^2 & \text{if } \lambda x_1+(1-\lambda)x_2 \leq 0 \\
0 & \text{otherwise}
\end{cases}$$- For the second case, it is trivial since $\lambda x_1^2 \geq 0$ must hold for $\lambda \in [0,1]$.
- For the first case though, we need to prove this inequality holds for $\lambda \in [0,1]$:
$$\begin{align}
\lambda x_1^2\geq (\lambda x_1+(1-\lambda)x_2)^2 &
\end{align}$$
…which I've been struggling with. I should probably be able to incorporate the inequalities $x_1 \leq 0$, $x_2 \geq 0$, and $\lambda x_1+(1-\lambda)x_2 \leq 0$.
- On LHS, substituting the function into the inequality:
Would appreciate someone to tell me what I'm missing, or if there's a better way to prove this function to be convex. Thanks!
Best Answer
You're almost finished. Regarding what you're struggling with, note that
$$\begin{equation}\begin{aligned} \lambda x_1^2 \geq (\lambda x_1+(1-\lambda)x_2)^2 \iff \\ (\sqrt{\lambda}x_1)^2 - (\lambda x_1+(1-\lambda)x_2)^2 \ge 0 \iff \\ (\color{blue}{\sqrt{\lambda}x_1 - (\lambda x_1+(1-\lambda)x_2)})(\color{green}{\sqrt{\lambda}x_1 + (\lambda x_1+(1-\lambda)x_2)}) \ge 0 \end{aligned}\end{equation}\tag{1}\label{eq1A}$$
The first factor (i.e., in $\color{blue}{\text{blue}}$) becomes
$$\begin{equation}\begin{aligned} \sqrt{\lambda}x_1 - (\lambda x_1+(1-\lambda)x_2) & = (\sqrt{\lambda} - \lambda)x_1 - (1- \lambda)x_2 \\ & = \sqrt{\lambda}(1 - \sqrt{\lambda})x_1 - (1- \lambda)x_2 \end{aligned}\end{equation}\tag{2}\label{eq2A}$$
Since $\sqrt{\lambda} \ge 0$, with $\lambda \in [0,1]$ we have $\sqrt{\lambda} \le 1 \; \to \; 1 - \sqrt{\lambda} \ge 0$, and $x_1 \le 0$, we get $\sqrt{\lambda}(1 - \sqrt{\lambda})x_1 \le 0$. Also, $1 - \lambda \ge 0$ and $x_2 \ge 0$, so $- (1- \lambda)x_2 \le 0$. Thus, overall, the value in \eqref{eq2A} (and thus the first factor in \eqref{eq1A}) is $\le 0$.
With the second factor in \eqref{eq1A} (i.e., in $\color{green}{\text{green}}$), since $\sqrt{\lambda}\ge 0$ and $x_1 \le 0$, we have $\sqrt{\lambda}x_1 \le 0$. Also, as you stated, $\lambda x_1+(1-\lambda)x_2 \le 0$. Thus, overall, this factor is $\le 0$.
Both factors in \eqref{eq1A} are $\le 0$, so their product is $\ge 0$, which means \eqref{eq1A} is true.
Since $x_1 \le 0$ and $\lambda x_1+(1-\lambda)x_2 \le 0$, a bit simpler alternative to \eqref{eq1A} is
$$\begin{equation}\begin{aligned} \lambda x_1^2 & \geq (\lambda x_1+(1-\lambda)x_2)^2 \iff \\ \lvert \sqrt{\lambda} x_1 \rvert & \geq \lvert \lambda x_1+(1-\lambda)x_2 \rvert \iff \\ -\sqrt{\lambda} x_1 & \geq -(\lambda x_1+(1-\lambda)x_2) \iff \\ 0 & \geq \sqrt{\lambda} x_1 -(\lambda x_1+(1-\lambda)x_2) \end{aligned}\end{equation}\tag{3}\label{eq3A}$$
Note the RHS is the first factor (i.e., in $\color{blue}{\text{blue}}$) of \eqref{eq1A}, so we can proceed as before with \eqref{eq2A}, but without later needing to handle the second factor in \eqref{eq1A} (i.e., in $\color{green}{\text{green}}$).