<commit_before>---
comments: true
title: Fenchel duality
updated: 2017-12-05 23:00
---
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 

$$		
	f^*(s) = \sup_{x \in \text{dom} f} (s^T x - f(x))
$$

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

>**Lemma** _Consider the following conditions:_
>
$$
\begin{align*}
	[1]~& f^*(s) =  s^Tx - f(x)\\
	[2]~& s \in \partial f(x)\\
	[3]~& x \in \partial f^*(s)
\end{align*}
$$
> 
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](http://xingyuzhou.org/talks/Fenchel_duality.pdf) (page 40).

<div class="divider"></div>

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](http://xingyuzhou.org/blog/notes/strong-convexity), we have 

$$
\begin{align*}
		\lVert s_x - s_y \rVert \ge \mu\lVert x-y \rVert ~\forall s_x\in \partial f(x), s_y\in \partial f(y)
\end{align*}
$$

Based on the previous lemma, we have

$$	
\begin{align*}
		\lVert s_x - s_y\rVert \ge \mu\lVert \nabla f^*(s_x)- \nabla f^*(s_y) \rVert
\end{align*}
$$

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](http://xingyuzhou.org/blog/notes/Lipschitz-gradient), we have 

$$
\begin{align*}
		(\nabla f(x) - \nabla f(y)^T(x-y) \ge \frac{1}{L} \lVert \nabla f(x)-\nabla f(y)\rVert^2
\end{align*}
$$

which implies based on the previous lemma 

$$	
\begin{align*}
		(s_x - s_y)^T (x-y) \ge \frac{1}{L} (s_x - s_y)~\forall x \in \partial f^*(s_x), y \in \partial f^*(s_y)
\end{align*}
$$

Hence, $$f^*$$ is strongly convex with parameter $$\frac{1}{L}$$ according to the previous post on [strong convexity](http://xingyuzhou.org/blog/notes/strong-convexity). $$\tag*{$\Box$}$$







<!-- Last time, we talked about [strong convexity](http://xingyuzhou.org/blog/notes/strong-convexity). Today, let us look at another important concept in convex optimization, named _Lipschitz continuous gradient_ condition, which is essential to ensuring convergence of many gradient decent based algorithms. The post is also mainly based on my course project report.  

It is worth noting that there exits a duality (Fenchel duality) between strong convexity and Lipschitz continuous gradient, which implies that once we have a good understanding of one, we may easily understand the other one. 

**Note:** Indeed, all the results in this post can be easily proved via the same method adopted in the post of strong convexity. This is the beauty of duality!

As usual, let's us first begin with the definition. 

A differentiable function $$f$$ is said to have an L-Lipschitz continuous gradient if for some $$L>0$$

$$
\lVert \nabla f(x) - \nabla f(y)\rVert \le L \lVert x-y\rVert,~\forall x,y.
$$

**Note:** The definition doesn't assume convexity of $$f$$. 
<commit_msg>Update typo<commit_after>---
comments: true
title: Fenchel duality
updated: 2017-12-05 23:00
---
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 

$$		
	f^*(s) = \sup_{x \in \text{dom} f} (s^T x - f(x))
$$

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

>**Lemma** _Consider the following conditions:_
>
$$
\begin{align*}
	[1]~& f^*(s) =  s^Tx - f(x)\\
	[2]~& s \in \partial f(x)\\
	[3]~& x \in \partial f^*(s)
\end{align*}
$$
> 
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](http://xingyuzhou.org/talks/Fenchel_duality.pdf) (page 40).

<div class="divider"></div>

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](http://xingyuzhou.org/blog/notes/strong-convexity), we have 

$$
\begin{align*}
		\lVert s_x - s_y \rVert \ge \mu\lVert x-y \rVert ~\forall s_x\in \partial f(x), s_y\in \partial f(y)
\end{align*}
$$

Based on the previous lemma, we have

$$	
\begin{align*}
		\lVert s_x - s_y\rVert \ge \mu\lVert \nabla f^*(s_x)- \nabla f^*(s_y) \rVert
\end{align*}
$$

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](http://xingyuzhou.org/blog/notes/Lipschitz-gradient), we have 

$$
\begin{align*}
		(\nabla f(x) - \nabla f(y)^T(x-y) \ge \frac{1}{L} \lVert \nabla f(x)-\nabla f(y)\rVert^2
\end{align*}
$$

which implies based on the previous lemma 

$$	
\begin{align*}
		(s_x - s_y)^T (x-y) \ge \frac{1}{L} \lVert s_x - s_y \rVert^2~\forall x \in \partial f^*(s_x), y \in \partial f^*(s_y)
\end{align*}
$$

Hence, $$f^*$$ is strongly convex with parameter $$\frac{1}{L}$$ according to the previous post on [strong convexity](http://xingyuzhou.org/blog/notes/strong-convexity). $$\tag*{$\Box$}$$







<!-- Last time, we talked about [strong convexity](http://xingyuzhou.org/blog/notes/strong-convexity). Today, let us look at another important concept in convex optimization, named _Lipschitz continuous gradient_ condition, which is essential to ensuring convergence of many gradient decent based algorithms. The post is also mainly based on my course project report.  

It is worth noting that there exits a duality (Fenchel duality) between strong convexity and Lipschitz continuous gradient, which implies that once we have a good understanding of one, we may easily understand the other one. 

**Note:** Indeed, all the results in this post can be easily proved via the same method adopted in the post of strong convexity. This is the beauty of duality!

As usual, let's us first begin with the definition. 

A differentiable function $$f$$ is said to have an L-Lipschitz continuous gradient if for some $$L>0$$

$$
\lVert \nabla f(x) - \nabla f(y)\rVert \le L \lVert x-y\rVert,~\forall x,y.
$$

**Note:** The definition doesn't assume convexity of $$f$$. 

{'fraction_non_alphanumeric': 0.14513339920948617, 'fraction_numerical': 0.008028656126482214, 'mean_word_length': 4.0543071161048685, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5197795', 'n_tokens_mistral': 2783, 'n_tokens_neox': 2533, 'n_words': 1075}