# Fenchel duality

Last time, we have mentioned that there exists a duality between strong convexity and Lipschitz continuous gradient. In this post, we will explore this duality, which is often called Fenchel duality.

This duality actually relates to the convex conjugate of a function. Thus, to begin with, we will first introduce the definition of conjugate function and some useful results.

The conjugate of a function $f$ is

Now, we will introduce several useful results on conjugate function.

Lemma Consider the following conditions:

Then we have the following results:

(i) For a general $f$, we have [1] $\iff$ [2] $\implies$ [3].

(ii) For a closed and convex $f$, we have [1]-[3] are all equivalent.

(iii) For a closed and strictly convex $f$, we have $\nabla f^*(s) = \arg\!\max_x(s^T x - f(x))$.

Proof: Please refer to my notes here (page 40).

Now, we are well prepared to prove the following theorem. The proof is quite simple once you have a good understanding of my previous posts on strong convexity and Lipschitz continuous gradient.

Theorem

(i) If $f$ is closed and strong convex with parameter $\mu$, then $f^*$ has a Lipschitz continuous gradient with parameter $\frac{1}{\mu}$.

(ii) If $f$ is convex and has a Lipschitz continuous gradient with parameter $L$, then $f^*$ is strong convex with parameter $\frac{1}{L}$.

Proof:

(1): By implication of strong convexity shown in the previous post on strong convexity, we have

Based on the previous lemma, we have

Hence, $f^*$ has a Lipschitz continuous gradient with $\frac{1}{\mu}$.

(2): By implication of Lipschitz continuous gradient for convex $f$ shown in the post of Lipschitz continuous gradient, we have

which implies based on the previous lemma

Hence, $f^*$ is strongly convex with parameter $\frac{1}{L}$ according to the previous post on strong convexity. $\tag*{\Box}$

THE END

Now, it’s time to take a break by appreciating the masterpiece of Monet.

The Poppy Field near Argenteuil

courtesy of www.Claude-Monet.com