proving convexity of dual function

Question

I've come up at a task which seems easy but I'm surely missing something or I might have got it wrong.

given the dual function defined as $f^*(x) = Sup_{y\in S} <y,x> - f(y)$, And a strong convex and continuous function $f:S->\mathbb{R}$.

If I am given $g(x) = (-1/b)f^*(-bx)$. How can I prove that $g(x)$ is concave? or in other words that $-g(x)$ is convex? Would like to hear some ideas, I tried using Fenchel's inequality but it didn't add up correctly, I think I missed something here.

Answer 1

Let $x_1,x_2$ be vectors and $\lambda_1,\lambda_2$ be nonnegative with $\lambda_1+\lambda_2=1$. First, for any vector $y$, \begin{align*} \langle y,\lambda_1x_1+\lambda_2x_2\rangle - f(y) &= \lambda_1\big(\langle y,x_1\rangle-f(y)\big) + \lambda_2\big(\langle y,x_2\rangle - f(y)\big)\\ &\leq \lambda_1f^*(x_1)+\lambda_2f^*(x_2) \end{align*} Taking the supremum over $y$ gives \begin{align*} f^*(\lambda_1x_1+\lambda_2x_2) = \sup_{y} \big( \langle y,\lambda_1x_1+\lambda_2x_2\rangle - f(y)\big) \leq \lambda_1f^*(x_1)+\lambda_2f^*(x_2) \end{align*} which shows that $f^*$ is convex.

Now let $b>0$. We show that $x\mapsto \tfrac{1}{b}f^*(-bx)$ is convex. Indeed, \begin{align*} \tfrac{1}{b}f^*\big(-b(\lambda_1x_1+\lambda_2x_2)\big) &= \tfrac{1}{b}f^*\big(\lambda_1(-bx_1)+\lambda_2(-bx_2)\big)\\ &\leq \tfrac{1}{b}\Big(\lambda_1f^*(-bx_1)+\lambda_2f^*(-bx_2) \Big)\\\ &= \lambda_1\big(\tfrac{1}{b}f^*(-bx_1)\big) + \lambda_2\big(\tfrac{1}{b}f^*(-bx_2)\big). \end{align*} This shows that your function $-g$ is convex, as requested.

Answer 2

The fact that $f^*$ is convex follows immediately from the fact that "the supremum of convex functions is convex".

For each $y \in S$, the function $x \mapsto \langle y,x \rangle - f(y)$ is convex. Thus, the function $$ f^*(x) = \sup_{y \in S} \, \langle y,x \rangle - f(y) $$ is convex.