Convex analysis (part II)

The convex conjugate

Let us start with the definition of the subdifferential of a convex function $f$ at a point $x\in C \subseteq \mathbb R^n$:

$$\begin{array}{rcl} \partial f(x) &=& \{y\in \mathbb R^n\,|\, f(z)\,\ge\, f(x)+\langle z-x,y\rangle, \,\forall z\in C\},\end{array}$$ We can rearrange terms in the condition as follows: $$\begin{array}{rcl} \partial f(x) &=& \{y\in\mathbb R^n\,|\, \langle z,y\rangle - f(z)\,\le\, \langle x,y\rangle - f(x), \,\forall z\in C\}.\end{array}$$ However, since the condition must hold for all $z$, it must equivalently hold for any $z$ that maximises the lower bound. Note that the maximum of that lower bound tightens the inequality exactly (take $z=x$). We can thus write the subdifferential as

We can now introduce the convex conjugate of a function (also sometimes known as the Fenchel-Legendre convex conjugate or a combination of those words).
In the sequel, we write $\overline{\mathbb R}$ the extended real line: $\overline{\mathbb R} = \mathbb R \cup \{\pm\infty\}$.

Note: it's easy to show that the convex conjugate of a function $f$ is always convex (even if the function $f$ is not convex).

We can now use the convex conjugate in (3): $$\begin{array}{rcl} \partial f(x) &=& \{ y\in\mathbb R^n \,|\, f^{\star}(y) \,=\, \langle x,y\rangle - f(x)\}, \end{array}$$ which is a convenient characterisation that will often be used.

Example: we can consider a simple (and yet quite useful) example for the convex conjugate: if we define $\psi(x):=\|x\|^2/2$, its convex conjugate is then

The problem in the right hand side is easy to solve: the objective function is differentiable and the FOC gives $y-z^\sharp = 0$ so that $\psi^\star(y)= \psi(y)$.

Another nice example is $f(x)=x\log(x)$, it's an easy exercise to show that $f^\star(y)=\exp(y-1)$ and $f^{\star\star}(x) = f(x)$.

Fenchel's inequality and the Fenchel-Moreau theorem

This inequality is directly implied by the definition of the convex conjugate.

Proving the theorem in full generality requires a bit of care (see references). It is however relatively straightforward to show that the result holds on $C^\circ$ (the interior of $C$) without requiring extra results. We will go about it in two parts:

1. show that $f(z)\ge f^{\star\star}(z)$ for all $z\in C$,

2. show that $f(z)\le f^{\star\star}(z)$ for all $z\in C^\circ$.

FMT (pt.1)

By definition of the convex conjugate,

but since $-f^\star(y)=\inf_{x\in C} [f(x)-\left\langle x,y\right\rangle]$, we have that for any $y$ and $z$, $$\begin{array}{rcl} \left\langle z,y\right\rangle - f^\star(y) &\le& \left\langle z-x,y\right\rangle + f(x), \quad\forall x\in C.\end{array}$$ In particular, for any $z\in C$, we can take $x=z$ so that $f^{\star\star}(z) \le f(z)$ on $C$.

FMT (pt.2)

Starting again from (8), we can write $$\begin{array}{rcl} f^{\star\star}(z) &\ge& \left\langle z,y\right\rangle - f^\star(y), \quad \forall y \in\mathbb R^n.\end{array}$$ If we now consider $x\in C^\circ$, we know that $\partial f(x)$ is non-empty and so can pick $y\in \partial f(x)$. But for such a $y$ using the characterisation of the subdifferential (5) we can write $$\begin{array}{rcl} f^\star(y) &=& \left\langle x, y\right\rangle - f(x)\end{array}$$ so that $f^{\star\star}(z) \ge \left\langle z-x, y\right\rangle + f(x)$. For $z\in C^\circ$ we can pick $x=z$ and get $f^{\star\star}(z)\ge f(z)$.

Subdifferential of the convex conjugate

Consider the definition of the subdifferential (5), for any $x\in C$ with $y\in \partial(x)$ we have $$\begin{array}{rcl} (x\in C, y\in\partial f(x)) &\Longleftrightarrow& f^\star(y)=\left\langle x, y\right\rangle-f(x).\end{array}$$ With exactly the same definition, we have for $x\in\partial f^\star(y)$ $$\begin{array}{rcl} x\in\partial f^\star(y) &\Longleftrightarrow& f^{\star\star}(x)=\left\langle x, y\right\rangle-f^\star(y),\end{array}$$ and the last equality can be rearranged to $f^\star(y)=\left\langle x,y\right\rangle-f^{\star\star}(x)$. In the case where $f\in\Gamma_0(C)$ then $f\equiv f^{\star\star}$ on $C$ by the Fenchel-Moreau theorem which gives the following result.

Using the inverse of the subdifferential operator on the left hand side of (14), we have that $x\in(\partial f)^{-1}(y)\cap C$ is equivalent to $x\in\partial f^\star(y)\cap C$ which exposes a close link between $(\partial f)^{-1}$ and $\partial f^\star$. This link becomes even more apparent in the unconstrained case.

Note: recall that, with the first order condition, a minimiser $x^\dagger$ is such that $0\in \partial f(x^\dagger)$ or $(\partial f)^{-1}(0) \ni x^\dagger$. We can now also write this $x^\dagger \in \partial f^\star(0)$, thereby expressing the minimiser in terms of the convex-conjugate. Of course it's not clear at this point whether this helps at all to find the minimiser but, as it turns out, it will.

Example: let's consider $f(x)=x\log(x)$ on $C = [0, 1]$. We know that $f^\star(y)=\exp(y-1)$. Both $f$ and $f^\star$ are differentiable so $\partial f(x)=\{\nabla f(x)\}$ with $\nabla f(x)=\log x +1$ on $C$ and $\partial f^\star(y)=\{\nabla f^\star(y)\}$ with $\nabla f^\star(y)=\exp(y-1)$ on $\mathbb R$.

Gathering the pieces, if we take $x\in C$ and $y=\nabla f(x)$, we have $$\begin{array}{rcl} y \,=\,\log x+1 &\Longrightarrow& x \,=\,\exp(y-1) \,=\,\nabla f^\star(y)\end{array}$$ and conversely if we consider a $y$ such that $\exp(y-1)\in C$ then $$\begin{array}{rcl} x \,=\,\exp(y-1) &\Longrightarrow& y \,=\,\log x + 1 \,=\,\nabla f(x)\end{array}$$ So that the equivalence (14) holds as expected.

Additional references

Note: in this page (and also further) we usually consider $C^\circ$ instead of $C$ to make the presentation simpler since we know that on $C^\circ$, subgradients exist and are bounded. Of course this is done at the expense of generality and some care is needed to generalise properly but the extra details did not seem particularly relevant at the level of this presentation. The references listed below show (and prove) the results in their full glory.

1. Hiriart-Urruty, A note on the Legendre-Fenchel transform of convex composite functions, 2006. – This is a more technical note that you may find interesting if you would like more details on convex conjugacy.

2. Mete Soner, Convex analysis and Fenchel-Moreau theorem, 2015. – Lecture notes covering convex conjugacy in more depth and proving rigorously the Fenchel-Moreau theorem.

See also the general references mentioned in the introduction.