Is the convex conjugate of the sum of infinity norm and Euclidean norm strictly convex?

Question

Is the following function $$f(x)=\sup_{y \in \mathbb{R}^n} \Big\{ x^\top y - \|y\|_\infty - \|y\|_2^2\Big\}$$ strictly convex?

Answer 1

You can write the function as $f(x) = (g+h)^*(y)$ with $g(y)=||y||_\infty$ and $h(y)=y^Ty$. This allows us to derive the following equivalence: $$f(x) = (g+h)^*(y)=\inf_z \{ g^*(z)+h^*(y-z) \} = \inf_z \left\{ \frac{1}{4}z^Tz : ||y-z||_1\leq 1\right\}.$$ The function value is $0$ around $y=0$ (as long as $||y||_1 \leq 1$).