9.18. Smoothness

Primary references for this section are [7].

9.18.1. L-Smooth Functions

Definition 9.80 (L-smooth functions)

For some $L\ge 0$, a function $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ is called $L$-smooth over a set $D\subseteq \mathbb{V}$ if it is differentiable over $D$ and satisfies

$$\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }\le L\Vert \mathbf{x}-\mathbf{y}\Vert \mathrm{\forall }\mathbf{x},\mathbf{y}\in D.$$

The constant $L$ is called the smoothness parameter.

• Since $f$ is differentiable over $D$, hence $D\subseteq \mathrm{int}\mathrm{dom}f$.

• If $f$ is $L$-smooth over the entire $\mathbb{V}$, we simply say that $f$ is $L$-smooth.

• $L$-smooth functions are also known as functions with Lipschitz gradient with constant $L$.

• The class of functions which are $L$-smooth over a set $D$ is denoted by $C_L^{1,1}(D)$.

• When $D=\mathbb{V}$, then the class is simply denoted as $C_L^{1,1}$.

• The class of functions which are $L$-smooth for some $L\ge 0$ (but $L$ may not be known), is denoted by $C^{1,1}$.

• By definition, if a function is $L_1$-smooth, then it is $L_2$-smooth for every $L_2\ge L_1$.

• Thus, it is often useful to identify the smallest possible value of $L$ for which a function is $L$-smooth.

Example 9.82 (Zero smoothness of affine functions)

Let $\mathbf{b}\in {\mathbb{V}}^{\ast }$ and $c\in \mathbb{R}$. Let $f:\mathbb{V}\to \mathbb{R}$ be given by:

$$f(\mathbf{x})=⟨\mathbf{x},\mathbf{b}⟩+c.$$

Then, $f$ is $0$-smooth.

To see this, we note that $\mathrm{\nabla }f(\mathbf{x})=\mathbf{b}$. Consequently,

$$\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }=\Vert \mathbf{b}-\mathbf{b}{\Vert }_{\ast }=\Vert \mathbf{0}{\Vert }_{\ast }=0\le 0\Vert \mathbf{x}-\mathbf{y}\Vert .$$

Theorem 9.263 (Smoothness of quadratic functions)

Let $\mathbf{A}\in {\mathbb{S}}^n$, $\mathbf{b}\in {\mathbb{R}}^n$ and $c\in \mathbb{R}$. Assume that ${\mathbb{R}}^n$ is endowed with ${\ell }_p$-norm for some $1\le p\le \mathrm{\infty }$. Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by:

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c.$$

Then, $f$ is $L$-smooth with $L=\Vert \mathbf{A}{\Vert }_{p,q}$ where $q\in [1,\mathrm{\infty }]$ is the conjugate exponent satisfying

$$\frac{1}{p}+\frac{1}{q}=1$$

and $\Vert \mathbf{A}{\Vert }_{p,q}$ is the induced norm given by

$$\Vert \mathbf{A}{\Vert }_{p,q}=sup\{\Vert \mathbf{A}\mathbf{x}{\Vert }_q|\Vert \mathbf{x}{\Vert }_p\le 1\}.$$

Proof. We note that the dual norm of ${\ell }_p$ norm is the ${\ell }_q$ norm. Now,

$$\begin{array}{rl}& \Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }\\ & =\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_q\\ & =\Vert \mathbf{A}\mathbf{x}+\mathbf{b}-\mathbf{A}\mathbf{y}-\mathbf{b}{\Vert }_q\\ & =\Vert \mathbf{A}\mathbf{x}-\mathbf{A}\mathbf{y}{\Vert }_q\\ & \le \Vert \mathbf{A}{\Vert }_{p,q}\Vert \mathbf{x}-\mathbf{y}{\Vert }_p.\end{array}$$

Thus, $f$ is $\Vert \mathbf{A}{\Vert }_{p,q}$ smooth.

We next show that $\Vert \mathbf{A}{\Vert }_{p,q}$ is the smallest smoothness parameter for $f$.

1. Assume that $f$ is $L$ smooth for some $L$.

2. By definition of $\Vert \mathbf{A}{\Vert }_{p,q}$, there exists a vector $\tilde{\mathbf{x}}$ such that $\Vert \tilde{\mathbf{x}}{\Vert }_p=1$ and

   $$\Vert \mathbf{A}\tilde{\mathbf{x}}{\Vert }_q=\Vert \mathbf{A}{\Vert }_{p,q}\Vert \tilde{\mathbf{x}}{\Vert }_p=\Vert \mathbf{A}{\Vert }_{p,q}.$$

3. Then,

   $$\begin{array}{rl}\Vert \mathbf{A}{\Vert }_{p,q}& =\Vert \mathbf{A}\tilde{\mathbf{x}}{\Vert }_q\\ & =\Vert \mathbf{A}\tilde{\mathbf{x}}+\mathbf{b}-\mathbf{A}\mathbf{0}-\mathbf{b}{\Vert }_q\\ & =\Vert \mathrm{\nabla }f(\tilde{\mathbf{x}})-\mathrm{\nabla }f(\mathbf{0}){\Vert }_q\\ & \le L\Vert \tilde{\mathbf{x}}-\mathbf{0}{\Vert }_p=L.\end{array}$$

4. Thus, $\Vert \mathbf{A}{\Vert }_{p,q}\le L$.

Thus, $\Vert \mathbf{A}{\Vert }_{p,q}$ is indeed the smallest smoothness parameter for $L$.

9.18.1.1. Descent Lemma

Theorem 9.264 (Descent lemma)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be $L$-smooth for some $L\ge 0$ over some convex set $D$. Then for any $\mathbf{x},\mathbf{y}\in D$,

$$f(\mathbf{y})\le f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+\frac{L}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

Proof. we proceed as follows:

1. By the fundamental theorem of calculus

   $$f(\mathbf{y})-f(\mathbf{x})={\int }_0^1⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))⟩dt.$$

2. By adding and subtracting $⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩$, we get:

   $$f(\mathbf{y})-f(\mathbf{x})=⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+{\int }_0^1⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))-\mathrm{\nabla }f(\mathbf{x})⟩dt.$$

3. This gives us

   $$\begin{array}{rl}& |f(\mathbf{y})-f(\mathbf{x})-⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩|\\ & =|{\int }_0^1⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))-\mathrm{\nabla }f(\mathbf{x})⟩dt|\\ & \le {\int }_0^1|⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))-\mathrm{\nabla }f(\mathbf{x})⟩|dt\\ & \le {\int }_0^1\Vert \mathbf{y}-\mathbf{x}\Vert \Vert \mathrm{\nabla }f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))-\mathrm{\nabla }f(\mathbf{x}){\Vert }_{\ast }dt& \text{ (a) }\\ & \le {\int }_0^1\Vert \mathbf{y}-\mathbf{x}\Vert tL\Vert \mathbf{y}-\mathbf{x}\Vert dt& \text{ (b) }\\ & ={\int }_0^{1}tL\Vert \mathbf{y}-\mathbf{x}{\Vert }^{2}dt\\ & =L\Vert \mathbf{y}-\mathbf{x}{\Vert }^2{\int }_0^{1}tdt\\ & =\frac{L}{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2.\end{array}$$

   • (a) is an application of Generalized Cauchy Schwartz inequality (Theorem 4.108}).

   • (b) is the application of $L$-smoothness of $f$ (Definition 9.80).

4. Thus,

   $$\begin{array}{rl}& |f(\mathbf{y})-f(\mathbf{x})-⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩|\le \frac{L}{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2\\ & ⟹f(\mathbf{y})-f(\mathbf{x})-⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩\le \frac{L}{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2\\ & ⟹f(\mathbf{y})\le f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+\frac{L}{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2.\end{array}$$

9.18.1.2. Characterization of $L$-Smooth Functions

Theorem 9.265 (Characterization of $L$-smooth functions)

Let $f:\mathbb{V}\to \mathbb{R}$ be convex and differentiable over $\mathbb{V}$. Let $L>0$. The following claims are equivalent:

1. $f$ is $L$-smooth.

2. $f(\mathbf{y})\le f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+\frac{L}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2\mathrm{\forall }\mathbf{x},\mathbf{y}\in \mathbb{V}$.

3. $f(\mathbf{y})\ge f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+\frac{1}{2L}\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }^2\mathrm{\forall }\mathbf{x},\mathbf{y}\in \mathbb{V}$.

4. $⟨\mathbf{x}-\mathbf{y},\mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y})⟩\ge \frac{1}{L}\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }^2\mathrm{\forall }\mathbf{x},\mathbf{y}\in \mathbb{V}$.

5. $f(t\mathbf{x}+(1-t)\mathbf{y})\ge tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{L}{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2\mathrm{\forall }\mathbf{x},\mathbf{y}\in \mathbb{V},t\in [0,1]$.

Proof. (1) $⟹$ (2). This is a direct implication of the descent lemma (Theorem 9.264).

(2) $⟹$ (3)

1. We are given that (2) is satisfied.

2. If $\mathrm{\nabla }f(\mathbf{x})=\mathrm{\nabla }f(\mathbf{y})$, then the inequality is trivial due to the convexity of $f$. Hence, we consider the case where $\mathrm{\nabla }f(\mathbf{x})\ne \mathrm{\nabla }f(\mathbf{y})$.

3. Fix a $\mathbf{x}\in \mathbb{V}$.

4. Consider a function $g_{\mathbf{x}}:\mathbb{V}\to \mathbb{R}$ given by

   $$g_{\mathbf{x}}(\mathbf{y})=f(\mathbf{y})-f(\mathbf{x})-⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩.$$

5. Then,

   $$\mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y})=\mathrm{\nabla }f(\mathbf{y})-\mathrm{\nabla }f(\mathbf{x}).$$

6. By hypothesis in property (2), for any $\mathbf{z}\in \mathbb{V}$

   $$f(\mathbf{z})\le f(\mathbf{y})+⟨\mathbf{z}-\mathbf{y},\mathrm{\nabla }f(\mathbf{y})⟩+\frac{L}{2}\Vert \mathbf{z}-\mathbf{y}{\Vert }^2.$$

7. Now,

   $$\begin{array}{rl}& g_{\mathbf{x}}(\mathbf{z})\\ & =f(\mathbf{z})-f(\mathbf{x})-⟨\mathbf{z}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩\\ & \le f(\mathbf{y})+⟨\mathbf{z}-\mathbf{y},\mathrm{\nabla }f(\mathbf{y})⟩+\frac{L}{2}\Vert \mathbf{z}-\mathbf{y}{\Vert }^2-f(\mathbf{x})-⟨\mathbf{z}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩\\ & =f(\mathbf{y})-f(\mathbf{x})-⟨\mathbf{z}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+⟨\mathbf{z}-\mathbf{y},\mathrm{\nabla }f(\mathbf{x})⟩-⟨\mathbf{z}-\mathbf{y},\mathrm{\nabla }f(\mathbf{x})⟩\\ & +⟨\mathbf{z}-\mathbf{y},\mathrm{\nabla }f(\mathbf{y})⟩+\frac{L}{2}\Vert \mathbf{z}-\mathbf{y}{\Vert }^2\\ & =f(\mathbf{y})-f(\mathbf{x})-⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+⟨\mathbf{z}-\mathbf{y},\mathrm{\nabla }f(\mathbf{y})-\mathrm{\nabla }f(\mathbf{x})⟩+\frac{L}{2}\Vert \mathbf{z}-\mathbf{y}{\Vert }^2\\ & =g_{\mathbf{x}}(\mathbf{y})+⟨\mathbf{z}-\mathbf{y},\mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y})⟩+\frac{L}{2}\Vert \mathbf{z}-\mathbf{y}{\Vert }^2.\end{array}$$

8. Thus, $g_{\mathbf{x}}$ also satisfies the inequality in property (2).

9. We note in particular that $\mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{x})=\mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$.

10. Since $g_{\mathbf{x}}$ is convex, hence $\mathbf{x}$ is the global minimizer of $g_{\mathbf{x}}$.

11. In other words,

    $$g_{\mathbf{x}}(\mathbf{x})\le g_{\mathbf{x}}(\mathbf{z})\mathrm{\forall }\mathbf{z}\in \mathbb{V}.$$

12. We can also see that $g_{\mathbf{x}}(\mathbf{x})=f(\mathbf{x})-f(\mathbf{x})-⟨\mathbf{x}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩=0$.

13. Let $\mathbf{y}\in \mathbb{V}$

14. Let $\mathbf{v}\in \mathbb{V}$ be the unit norm vector satisfying $\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }=⟨\mathbf{v},\mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y})⟩$.

15. Choose

    $$\mathbf{z}=\mathbf{y}-\frac{\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }}{L}\mathbf{v}.$$

16. Then,

    $$0=g_{\mathbf{x}}(\mathbf{x})\le g_{\mathbf{x}}(\mathbf{z})=g_{\mathbf{x}}(\mathbf{y}-\frac{\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }}{L}\mathbf{v}).$$

17. Using property (2) on $g_{\mathbf{x}}(\mathbf{z})$, we get

    $$\begin{array}{rl}0& \le g_{\mathbf{x}}(\mathbf{z})\\ & \le g_{\mathbf{x}}(\mathbf{y})+⟨\mathbf{z}-\mathbf{y},\mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y})⟩+\frac{L}{2}\Vert \mathbf{z}-\mathbf{y}{\Vert }^2\\ & =g_{\mathbf{x}}(\mathbf{y})-\frac{\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }}{L}⟨\mathbf{v},\mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y})⟩+\frac{L}{2}{\Vert \frac{\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }}{L}\mathbf{v}\Vert }^2\\ & =g_{\mathbf{x}}(\mathbf{y})-\frac{\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }}{L}\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }+\frac{1}{2L}\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }^2\\ & =g_{\mathbf{x}}(\mathbf{y})-\frac{1}{2L}\Vert \mathrm{\nabla }{g}_{\mathbf{x}}(\mathbf{y}){\Vert }_{\ast }^2\\ & =f(\mathbf{y})-f(\mathbf{x})-⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩-\frac{1}{2L}\Vert \mathrm{\nabla }f(\mathbf{y})-\mathrm{\nabla }f(\mathbf{x}){\Vert }_{\ast }^2.\end{array}$$

18. Simplifying this, we get

    $$f(\mathbf{y})\ge f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+\frac{1}{2L}\Vert \mathrm{\nabla }f(\mathbf{y})-\mathrm{\nabla }f(\mathbf{x}){\Vert }_{\ast }^2$$

    as desired.

(3) $⟹$ (4)

1. For $\mathbf{x},\mathbf{y}$, the property (3) gives us:

   $$f(\mathbf{y})\ge f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+\frac{1}{2L}\Vert \mathrm{\nabla }f(\mathbf{y})-\mathrm{\nabla }f(\mathbf{x}){\Vert }_{\ast }^2.$$

2. For $\mathbf{y},\mathbf{x}$, the property (3) gives us:

   $$f(\mathbf{x})\ge f(\mathbf{y})+⟨\mathbf{x}-\mathbf{y},\mathrm{\nabla }f(\mathbf{y})⟩+\frac{1}{2L}\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }^2.$$

3. Adding the two inequalities and canceling the term $f(\mathbf{x})+f(\mathbf{y})$ gives us

   $$0\ge ⟨\mathbf{x}-\mathbf{y},\mathrm{\nabla }f(\mathbf{y})-f(\mathbf{x})⟩+\frac{1}{L}\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }^2.$$

4. Rearranging, we get

   $$⟨\mathbf{x}-\mathbf{y},\mathrm{\nabla }f(\mathbf{x})-f(\mathbf{y})⟩\ge \frac{1}{L}\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }^2$$

   as desired.

(4) $⟹$ (1)

1. When $\mathrm{\nabla }f(\mathbf{x})=\mathrm{\nabla }f(\mathbf{y})$, then the Lipschitz condition in (1) is trivial. Hence, we consider the case where $\mathrm{\nabla }f(\mathbf{x})\ne \mathrm{\nabla }f(\mathbf{y})$.

2. By generalized Cauchy Schwartz inequality (Theorem 4.108)

   $$⟨\mathbf{x}-\mathbf{y},\mathrm{\nabla }f(\mathbf{x})-f(\mathbf{y})⟩\le \Vert \mathbf{x}-\mathbf{y}\Vert \Vert f(\mathbf{x})-f(\mathbf{y}){\Vert }_{\ast }.$$

3. Thus, combining with hypothesis (4), we obtain

   $$\frac{1}{L}\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }^2\le \Vert \mathbf{x}-\mathbf{y}\Vert \Vert f(\mathbf{x})-f(\mathbf{y}){\Vert }_{\ast }.$$

4. Since $\mathrm{\nabla }f(\mathbf{x})\ne \mathrm{\nabla }f(\mathbf{y})$, hence $\Vert f(\mathbf{x})-f(\mathbf{y}){\Vert }_{\ast }>0$.

5. Canceling it from both sides, we get

   $$\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }\le L\Vert \mathbf{x}-\mathbf{y}\Vert$$

   as desired.

We have shown so far that (1), (2), (3) and (4) are equivalent statements. We are left with showing that (5) is equivalent to the other statements.

(2) $⟹$ (5)

1. Pick $\mathbf{x},\mathbf{y}\in \mathbb{V}$ and $t\in [0,1]$.

2. Let $\mathbf{z}=t\mathbf{x}+(1-t)\mathbf{y}$.

3. By hypothesis (2),

   $$\begin{array}{rl}& f(\mathbf{x})\le f(\mathbf{z})+⟨\mathbf{x}-\mathbf{z},\mathrm{\nabla }f(\mathbf{z})⟩+\frac{L}{2}\Vert \mathbf{x}-\mathbf{z}{\Vert }^2;\\ & f(\mathbf{y})\le f(\mathbf{z})+⟨\mathbf{y}-\mathbf{z},\mathrm{\nabla }f(\mathbf{z})⟩+\frac{L}{2}\Vert \mathbf{y}-\mathbf{z}{\Vert }^2.\end{array}$$

4. Note that $\mathbf{x}-\mathbf{z}=(1-t)(\mathbf{x}-\mathbf{y})$ and $\mathbf{y}-\mathbf{z}=t(\mathbf{y}-\mathbf{x})$.

5. Thus, the previous two inequalities are same as

   $$\begin{array}{rl}& f(\mathbf{x})\le f(\mathbf{z})+(1-t)⟨\mathbf{x}-\mathbf{y},\mathrm{\nabla }f(\mathbf{z})⟩+\frac{L(1-t{)}^2}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2;\\ & f(\mathbf{y})\le f(\mathbf{z})+t⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{z})⟩+\frac{L{t}^2}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.\end{array}$$

6. Multiplying the first inequality by $t$, the second by $(1-t)$ and adding, we get

   $$tf(\mathbf{x})+(1-t)f(\mathbf{y})\le f(\mathbf{z})+\frac{Lt(1-t)}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

7. Rearranging, we get

   $$f(t\mathbf{x}+(1-t)\mathbf{y})=f(\mathbf{z})\ge tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{L}{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

(5) $⟹$ (2)

1. Pick $\mathbf{x},\mathbf{y}\in \mathbb{V}$ and $t\in (0,1)$.

2. By hypothesis in inequality (5)

   $$f(t\mathbf{x}+(1-t)\mathbf{y})\ge tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{L}{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

3. Rearranging the terms, we obtain

   $$\begin{array}{rl}& (1-t)f(\mathbf{y})\le f(t\mathbf{x}+(1-t)\mathbf{y})-tf(\mathbf{x})+\frac{L}{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2\\ & ⟺(1-t)f(\mathbf{y})\le f(t\mathbf{x}+(1-t)\mathbf{y})-f(\mathbf{x})+(1-t)f(\mathbf{x})+\frac{L}{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2\\ & ⟺f(\mathbf{y})\le f(\mathbf{x})+\frac{f(t\mathbf{x}+(1-t)\mathbf{y})-f(\mathbf{x})}{1-t}+\frac{L}{2}t\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.\end{array}$$

   Division by $(1-t)$ is fine since $(1-t)\in (0,1)$.

4. Recalling the definition of directional derivative (Definition 9.70):

   $$\begin{array}{rl}& \underset{t\to 1^{-}}{lim}\frac{f(t\mathbf{x}+(1-t)\mathbf{y})-f(\mathbf{x})}{1-t}\\ & =\underset{s\to 0^{+}}{lim}\frac{f((1-s)\mathbf{x}+s\mathbf{y})-f(\mathbf{x})}{s}\\ & =\underset{s\to 0^{+}}{lim}\frac{f(\mathbf{x}+s(\mathbf{y}-\mathbf{x}))-f(\mathbf{x})}{s}\\ & =f^{\prime }(\mathbf{x};\mathbf{y}-\mathbf{x}).\end{array}$$

5. Since the previous inequality is valid for every $t\in (0,1)$, taking the limit to $t\to 1^{-}$ on the R.H.S., we obtain

   $$f(\mathbf{y})\le f(\mathbf{x})+f^{\prime }(\mathbf{x};\mathbf{y}-\mathbf{x})+\frac{L}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

6. Recall from Theorem 9.203 that $f^{\prime }(\mathbf{x};\mathbf{y}-\mathbf{x})=⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩$.

7. Thus, we get:

   $$f(\mathbf{y})\le f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩+\frac{L}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

   as desired.

9.18.1.3. Second Order Characterization

We now restrict our attention to the vector space ${\mathbb{R}}^n$ equipped with an ${\ell }_p$ norm with $p\ge 1$.

Theorem 9.266 ($L$-smoothness and the boundedness of the Hessian)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a twice continuously differentiable function over ${\mathbb{R}}^n$. Then, for any $L\ge 0$, the following claims are equivalent:

1. $f$ is $L$-smooth w.r.t. the ${\ell }_p$-norm ($p\in [1,\mathrm{\infty }]$).

2. $\Vert {\mathrm{\nabla }}^{2}f(\mathbf{x}){\Vert }_{p,q}\le L$ for any $\mathbf{x}\in {\mathbb{R}}^n$ where $q\ge 1$ satisfies $\frac{1}{p}+\frac{1}{q}=1$.

Proof. (2) $⟹$ (1)

1. We are given that $\Vert {\mathrm{\nabla }}^{2}f(\mathbf{x}){\Vert }_{p,q}\le L$ for any $\mathbf{x}\in {\mathbb{R}}^n$.

2. By the fundamental theorem of calculus

   $$\begin{array}{rl}\mathrm{\nabla }f(\mathbf{y})-\mathrm{\nabla }f(\mathbf{x})& ={\int }_0^1{\mathrm{\nabla }}^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))(\mathbf{y}-\mathbf{x})dt\\ & =({\int }_0^1{\mathrm{\nabla }}^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))dt)(\mathbf{y}-\mathbf{x}).\end{array}$$

3. Taking the (dual)-norm on both sides

   $$\begin{array}{rl}\Vert \mathrm{\nabla }f(\mathbf{y})-\mathrm{\nabla }f(\mathbf{x}){\Vert }_q& ={\Vert ({\int }_0^1{\mathrm{\nabla }}^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))dt)(\mathbf{y}-\mathbf{x})\Vert }_q\\ & \le {\Vert {\int }_0^1{\mathrm{\nabla }}^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))dt\Vert }_{p,q}\Vert \mathbf{y}-\mathbf{x}{\Vert }_p\\ & \le ({\int }_0^1\Vert {\mathrm{\nabla }}^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x})){\Vert }_{p,q}dt)\Vert \mathbf{y}-\mathbf{x}{\Vert }_p\\ & \le \left({\int }_0^{1}Ldt\right)\Vert \mathbf{y}-\mathbf{x}{\Vert }_p\\ & =L\Vert \mathbf{y}-\mathbf{x}{\Vert }_p.\end{array}$$

4. Thus, $\Vert \mathrm{\nabla }f(\mathbf{y})-\mathrm{\nabla }f(\mathbf{x}){\Vert }_q\le L\Vert \mathbf{y}-\mathbf{x}{\Vert }_p$ as desired.

(1) $⟹$ (2)

1. We are given that $f$ is $L$ smooth with ${\ell }_p$ norm.

2. By fundamental theorem of calculus, for any $\mathbf{d}\in {\mathbb{R}}^n$ and $s>0$,

   $$\mathrm{\nabla }f(\mathbf{x}+s\mathbf{d})-\mathrm{\nabla }f(\mathbf{x})={\int }_0^s{\mathrm{\nabla }}^{2}f(\mathbf{x}+t\mathbf{d})\mathbf{d}dt.$$

3. Taking $q$ norm on both sides

   $${\Vert ({\int }_0^s{\mathrm{\nabla }}^{2}f(\mathbf{x}+t\mathbf{d})dt)\mathbf{d}\Vert }_q=\Vert \mathrm{\nabla }f(\mathbf{x}+s\mathbf{d})-\mathrm{\nabla }f(\mathbf{x}){\Vert }_q\le L\Vert \mathbf{x}+s\mathbf{d}-\mathbf{x}{\Vert }_p=sL\Vert \mathbf{d}{\Vert }_p.$$

4. Dividing by $s$ on both sides and taking the limit $s\to 0^{+}$, we get

   $$\Vert {\mathrm{\nabla }}^{2}f(\mathbf{x})\mathbf{d}{\Vert }_q\le L\Vert \mathbf{d}{\Vert }_p.$$

5. Since this is valid for every $\mathbf{d}\in {\mathbb{R}}^n$, hence

   $$\Vert {\mathrm{\nabla }}^{2}f(\mathbf{x}){\Vert }_{p,q}\le L.$$

Corollary 9.27 ($L$-smoothness and largest eigenvalue of Hessian)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a twice continuously differentiable convex function over ${\mathbb{R}}^n$. Then $f$ is $L$-smooth w.r.t. ${\ell }_2$-norm if and only if

$${\lambda }_{max}({\mathrm{\nabla }}^{2}f(\mathbf{x}))\le L\mathrm{\forall }\mathbf{x}\in {\mathbb{R}}^n.$$

Proof. Since $f$ is convex, hence it follows that ${\mathrm{\nabla }}^{2}f(\mathbf{x})⪰\mathbf{O}$ for every $\mathbf{x}$. Thus,

$$\Vert {\mathrm{\nabla }}^{2}f(\mathbf{x}){\Vert }_{2,2}=\sqrt{{\lambda }_{max}({\mathrm{\nabla }}^{2}f(\mathbf{x}{)}^2)}={\lambda }_{max}({\mathrm{\nabla }}^{2}f(\mathbf{x})).$$

From Theorem 9.266, $f$ is $L$-smooth is equivalent to the condition that

$${\lambda }_{max}({\mathrm{\nabla }}^{2}f(\mathbf{x}))=\Vert {\mathrm{\nabla }}^{2}f(\mathbf{x}){\Vert }_{2,2}\le L.$$

9.18.2. Strong Convexity

Definition 9.81 (Strong convexity)

A function $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ is called $\sigma$-strongly convex for $\sigma >0$ if $\mathrm{dom}f$ is convex and the following holds for any $\mathbf{x},\mathbf{y}\in \mathrm{dom}f$ and $t\in [0,1]$:

(9.10)$$f(t\mathbf{x}+(1-t)\mathbf{y})\le tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{\sigma }{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

9.18.2.1. Strong Convexity $⟹$ Convexity

Strongly convex functions are convex. In fact, we have a stronger result available.

Theorem 9.267 (Strong convexity and convexity)

Assume that the ambient space $\mathbb{V}$ is Euclidean.

A function $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ is $\sigma$-strongly convex if and only if the function $f(\cdot )-\frac{\sigma }{2}\Vert \cdot {\Vert }^2$ is convex.

Proof. Let us define a function $g:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ as

$$g(\mathbf{x})=f(\mathbf{x})=\frac{\sigma }{2}\Vert \mathbf{x}{\Vert }^2.$$

We need to show that $f$ is $\sigma$-strongly convex if and only if $g$ is convex.

1. We first note that $\mathrm{dom}g=\mathrm{dom}f$.

2. Thus, $\mathrm{dom}g$ is convex if and only if $\mathrm{dom}f$ is convex.

3. Now, $g$ is convex if and only if $\mathrm{dom}g=\mathrm{dom}f$ is convex and for any $\mathbf{x},\mathbf{y}\in \mathrm{dom}f$ and $t\in (0,1)$

   $$g(t\mathbf{x}+(1-t)\mathbf{y})\le tg(\mathbf{x})+(1-t)g(\mathbf{y}).$$

4. Now,

   $$\begin{array}{rl}& g(t\mathbf{x}+(1-t)\mathbf{y})\le tg(\mathbf{x})+(1-t)g(\mathbf{y})\\ ⟺& f(t\mathbf{x}+(1-t)\mathbf{y})-\frac{\sigma }{2}\Vert t\mathbf{x}+(1-t)\mathbf{y}{\Vert }^2\\ & \le tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{\sigma }{2}[t\Vert \mathbf{x}{\Vert }^2+(1-t)\Vert \mathbf{y}{\Vert }^2]\\ ⟺& f(t\mathbf{x}+(1-t)\mathbf{y})\le tf(\mathbf{x})+(1-t)f(\mathbf{y})\\ & +\frac{\sigma }{2}[\Vert t\mathbf{x}+(1-t)\mathbf{y}{\Vert }^2-t\Vert \mathbf{x}{\Vert }^2-(1-t)\Vert \mathbf{y}{\Vert }^2].\end{array}$$

5. Since the norm is Euclidean, hence

   $$\begin{array}{rl}& \Vert t\mathbf{x}+(1-t)\mathbf{y}{\Vert }^2-t\Vert \mathbf{x}{\Vert }^2-(1-t)\Vert \mathbf{y}{\Vert }^2\\ & =⟨t\mathbf{x}+(1-t)\mathbf{y},t\mathbf{x}+(1-t)\mathbf{y}⟩-t\Vert \mathbf{x}{\Vert }^2-(1-t)\Vert \mathbf{y}{\Vert }^2\\ & =t^2\Vert \mathbf{x}{\Vert }^2+(1-t{)}^2\Vert \mathbf{y}{\Vert }^2+2t(1-t)⟨\mathbf{x},\mathbf{y}⟩-t\Vert \mathbf{x}{\Vert }^2-(1-t)\Vert \mathbf{y}{\Vert }^2\\ & =-t(1-t)\Vert \mathbf{x}{\Vert }^2-t(1-t)\Vert \mathbf{y}{\Vert }^2+2t(1-t)⟨\mathbf{x},\mathbf{y}⟩\\ & =-t(1-t)(\Vert \mathbf{x}{\Vert }^2+\Vert \mathbf{y}{\Vert }^2-2⟨\mathbf{x},\mathbf{y}⟩)\\ & =-t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.\end{array}$$

6. Thus, the convexity inequality for $g$ is equivalent to

   $$f(t\mathbf{x}+(1-t)\mathbf{y})\le tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{\sigma }{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2$$

   which is nothing but the $\sigma$-strong convexity condition of $f$.

9.18.2.2. Quadratic Functions

Theorem 9.268 (Strong convexity of quadratic functions)

Let $\mathbf{A}\in {\mathbb{S}}^n$, $\mathbf{b}\in {\mathbb{R}}^n$ and $c\in \mathbb{R}$. Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by:

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c.$$

Then $f$ is $\sigma$-strongly convex if and only if $\mathbf{A}$ is positive definite and $\sigma \le {\lambda }_{min}(\mathbf{A})$.

Proof. Due to Theorem 9.267, $f$ is strongly convex with $\sigma >0$ if and only if $g(\mathbf{x})=f(\mathbf{x})-\frac{\sigma }{2}\Vert \mathbf{x}{\Vert }^2$ is convex.

1. We note that

   $$\begin{array}{rl}g(\mathbf{x})& =\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c-\frac{\sigma }{2}\Vert \mathbf{x}{\Vert }^2\\ & =\frac{1}{2}{\mathbf{x}}^T(\mathbf{A}-\sigma \mathbf{I})\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c.\end{array}$$

2. As shown in Example 9.40, $g$ is convex if and only if $\mathbf{A}-\sigma \mathbf{I}⪰\mathbf{O}$.

3. This is equivalent to $\sigma \le {\lambda }_{min}(\mathbf{A})$.

9.18.2.3. Coerciveness

Theorem 9.269 (Strong convexity and coerciveness)

Assume that the ambient space $\mathbb{V}$ is Euclidean. Assume that $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ is a Fréchet-differentiable function. If $f$ is $\sigma$-strongly convex, then it is coercive.

Proof. We proceed as follows.

1. Define

   $$g(\mathbf{x})=f(\mathbf{x})-\frac{\sigma }{2}\Vert \mathbf{x}{\Vert }^2.$$

2. By Theorem 9.267, $g$ is convex.

3. Since $f$ is differentiable, hence $g$ is also differentiable.

4. Specifically, $\mathrm{\nabla }g(\mathbf{x})=\mathrm{\nabla }f(\mathbf{x})-\sigma \mathbf{x}$.

5. Fix some $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$.

6. Then $\partial g(\mathbf{x})=\{\mathrm{\nabla }g(\mathbf{x})\}$.

7. By subgradient inequality, for any $\mathbf{y}\in \mathbb{V}$,

   $$g(\mathbf{y})\ge g(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }g(\mathbf{x})⟩.$$

8. Expanding $g$ and $\mathrm{\nabla }g$:

   $$f(\mathbf{y})-\frac{\sigma }{2}\Vert \mathbf{y}{\Vert }^2\ge f(\mathbf{x})-\frac{\sigma }{2}\Vert \mathbf{x}{\Vert }^2+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})-\sigma \mathbf{x}⟩.$$

9. Let $\mathbf{v}=f(\mathbf{x})-\sigma \mathbf{x}$.

10. Rearranging terms

    $$f(\mathbf{y})\ge \frac{\sigma }{2}\Vert \mathbf{y}{\Vert }^2+⟨\mathbf{y},\mathbf{v}⟩+K_{\mathbf{x}}$$

    where $K_{\mathbf{x}}=f(\mathbf{x})-\frac{\sigma }{2}\Vert \mathbf{x}{\Vert }^2-⟨\mathbf{x},\mathbf{v}⟩$.

11. We note that the term $K_{\mathbf{x}}$ depends solely on $\mathbf{x}$ which is fixed. Hence $K_{\mathbf{x}}$ is a fixed quantity.

12. By Cauchy-Schwarz inequality

    $$⟨\mathbf{y},\mathbf{v}⟩\ge -\Vert \mathbf{v}\Vert \Vert \mathbf{y}\Vert .$$

13. Hence

    $$f(\mathbf{y})\ge \frac{\sigma }{2}\Vert \mathbf{y}{\Vert }^2-\Vert \mathbf{v}\Vert \Vert \mathbf{y}\Vert +K_{\mathbf{x}}.$$

14. It is easy to see that, the R.H.S. goes to $\mathrm{\infty }$ as $\Vert \mathbf{y}\Vert \to \mathrm{\infty }$.

15. Hence $f$ is coercive.

9.18.2.4. Sum Rule

Theorem 9.270 (Sum of strongly convex and convex functions)

Let $f$ be $\sigma$-strongly convex and $g$ be convex. Then $f+g$ is $\sigma$-strongly convex.

Proof. Since both $f$ and $g$ are convex, hence their domains are convex. Hence, $\mathrm{dom}(f+g)=\mathrm{dom}f\cap \mathrm{dom}g$ is also convex.

We further need to show that $f+g$ satisfies (9.10).

1. Let $\mathbf{x},\mathbf{y}\in \mathbb{V}$ and $t\in (0,1)$.

2. Since $f$ is $\sigma$-strongly convex, hence

   $$f(t\mathbf{x}+(1-t)\mathbf{y})\le tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{\sigma }{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

3. Since $g$ is convex, hence

   $$g(t\mathbf{x}+(1-t)\mathbf{y})\le tg(\mathbf{x})+(1-t)g(\mathbf{y}).$$

4. Then,

   $$\begin{array}{rl}& (f+g)(t\mathbf{x}+(1-t)\mathbf{y})\\ & =f(t\mathbf{x}+(1-t)\mathbf{y})+g((t\mathbf{x}+(1-t)\mathbf{y}))\\ & \le f(t\mathbf{x}+(1-t)\mathbf{y})\le tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{\sigma }{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2+tg(\mathbf{x})+(1-t)g(\mathbf{y})\\ & =t(f+g)(\mathbf{x})+(1-t)(f+g)(\mathbf{y})-\frac{\sigma }{2}t(1-t)\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.\end{array}$$

5. Thus, $f+g$ is also $\sigma$-strongly convex.

Example 9.83 (Strong convexity of $\frac{1}{2}|\cdot {|}^2+I_C$)

Let $\mathbb{V}$ be a Euclidean space.

1. The function $\frac{1}{2}\Vert \mathbf{x}{\Vert }^2$ is 1-strongly convex due to Theorem 9.268.

2. Let $C$ be a convex set.

3. Then, the indicator function $I_C$ is convex.

4. Due to Theorem 9.270, the function

   $$g(\mathbf{x})=\frac{1}{2}\Vert \mathbf{x}{\Vert }^2+I_C(\mathbf{x})$$

   is also 1-strongly convex.

9.18.2.5. First Order Characterization

Recall that $\mathrm{dom}(\partial f)$ denotes the set of points at which $f$ is subdifferentiable.

Theorem 9.271 (First order characterization of strong convexity)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper closed and convex function. For a given $\sigma >0$, the following statements are equivalent.

1. $f$ is $\sigma$-strongly convex.

2. For every $\mathbf{x}\in \mathrm{dom}(\partial f)$, $\mathbf{y}\in \mathrm{dom}f$ and $\mathbf{g}\in \partial f(\mathbf{x})$, the following holds true

   $$f(\mathbf{y})\ge f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathbf{g}⟩+\frac{\sigma }{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2.$$

3. For any $\mathbf{x},\mathbf{y}\in \mathrm{dom}(\partial f)$ and ${\mathbf{g}}_{\mathbf{x}}\in \partial f(\mathbf{x})$, ${\mathbf{g}}_{\mathbf{y}}\in \partial f(\mathbf{x})$, the following holds true:

   $$⟨\mathbf{x}-\mathbf{y},{\mathbf{g}}_{\mathbf{x}}-{\mathbf{g}}_{\mathbf{y}}⟩\ge \sigma \Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

Proof. We shall prove the equivalence of these statements in the following order. $(2)⟹(1)$, $(1)⟹(3)$, $(3)⟹(2)$.

(2) $⟹$ (1)

1. We assume that (2) is true.

2. Let $\mathbf{x},\mathbf{y}\in \mathrm{dom}f$ and $t\in (0,1)$.

3. We need to show that (9.10) holds for $f$.

4. Since $\mathrm{dom}f$ is convex, its relative interior is not empty (see Theorem 9.142).

5. Let $\mathbf{z}\in \mathrm{ri}\mathrm{dom}f$.

6. Choose some $\alpha \in (0,1]$.

7. Let $\tilde{\mathbf{x}}=(1-\alpha )\mathbf{x}+\alpha \mathbf{z}$.

8. By the line segment property (Theorem 9.143), $\tilde{\mathbf{x}}\in \mathrm{ri}\mathrm{dom}f$.

9. Let ${\mathbf{x}}_t=t\tilde{\mathbf{x}}+(1-t)\mathbf{y}$.

10. Again, by the line segment property, ${\mathbf{x}}_t\in \mathrm{ri}\mathrm{dom}f$.

11. Since $f$ is a proper convex function, hence the subdifferential of $f$ at relative interior points is nonempty (Theorem 9.217).

12. Thus, $\partial f({\mathbf{x}}_t)\ne \varnothing$ and ${\mathbf{x}}_t\in \mathrm{dom}(\partial f)$.

13. Take some $\mathbf{g}\in \partial f({\mathbf{x}}_t)$.

14. By hypothesis (2)

    $$f(\tilde{\mathbf{x}})\ge f({\mathbf{x}}_t)+⟨\tilde{\mathbf{x}}-{\mathbf{x}}_t,\mathbf{g}⟩+\frac{\sigma }{2}\Vert \tilde{\mathbf{x}}-{\mathbf{x}}_t{\Vert }^2.$$

15. Substituting ${\mathbf{x}}_t=t\tilde{\mathbf{x}}+(1-t)\mathbf{y}$, we have $\tilde{\mathbf{x}}-{\mathbf{x}}_t=(1-t)(\tilde{\mathbf{x}}-\mathbf{y})$. Thus,

    $$f(\tilde{\mathbf{x}})\ge f({\mathbf{x}}_t)+(1-t)⟨\tilde{\mathbf{x}}-\mathbf{y},\mathbf{g}⟩+\frac{\sigma (1-t{)}^2}{2}\Vert \tilde{\mathbf{x}}-\mathbf{y}{\Vert }^2.$$

16. Similarly, by hypothesis (2)

    $$f(\mathbf{y})\ge f({\mathbf{x}}_t)+⟨\mathbf{y}-{\mathbf{x}}_t,\mathbf{g}⟩+\frac{\sigma }{2}\Vert \mathbf{y}-{\mathbf{x}}_t{\Vert }^2.$$

17. $\mathbf{y}-{\mathbf{x}}_t=\mathbf{y}-t\tilde{\mathbf{x}}-(1-t)\mathbf{y}=t(\mathbf{y}-\tilde{\mathbf{x}})$.

18. This gives us,

    $$f(\mathbf{y})\ge f({\mathbf{x}}_t)+t⟨\mathbf{y}-\tilde{\mathbf{x}},\mathbf{g}⟩+\frac{\sigma t^2}{2}\Vert \mathbf{y}-\tilde{\mathbf{x}}{\Vert }^2.$$

19. Multiplying the first inequality by $t$ and the second one by $(1-t)$ and adding them together, we get

    $$tf(\tilde{\mathbf{x}})+(1-t)f(\mathbf{y})\ge f({\mathbf{x}}_t)+\frac{\sigma t(1-t)}{2}\Vert \tilde{\mathbf{x}}-\mathbf{y}{\Vert }^2.$$

20. Thus,

    $$f(t\tilde{\mathbf{x}}+(1-t)\mathbf{y})=f({\mathbf{x}}_t)\le tf(\tilde{\mathbf{x}})+(1-t)f(\mathbf{y})-\frac{\sigma t(1-t)}{2}\Vert \tilde{\mathbf{x}}-\mathbf{y}{\Vert }^2.$$

21. Expanding $\tilde{\mathbf{x}}$,

    $$\begin{array}{rl}t\tilde{\mathbf{x}}+(1-t)\mathbf{y}& =t((1-\alpha )\mathbf{x}+\alpha \mathbf{z})+(1-t)\mathbf{y}\\ & =t(1-\alpha )\mathbf{x}+(1-t)\mathbf{y}+t\alpha \mathbf{z}.\end{array}$$

22. Define $g_1(\alpha )=f(t\tilde{\mathbf{x}}+(1-t)\mathbf{y})=f(t(1-\alpha )\mathbf{x}+(1-t)\mathbf{y}+t\alpha \mathbf{z})$.

23. Define $g_2(\alpha )=f(\tilde{\mathbf{x}})=f((1-\alpha )\mathbf{x}+\alpha \mathbf{z})$.

24. Substituting these into the previous inequality, we obtain

    $$g_1(\alpha )\le t{g}_2(\alpha )+(1-t)f(\mathbf{y})-\frac{\sigma t(1-t)}{2}\Vert (1-\alpha )\mathbf{x}+\alpha \mathbf{z}-\mathbf{y}{\Vert }^2.$$

25. The functions $g_1$ and $g_2$ are one dimensional, proper, closed and convex functions.

26. By Theorem 9.173, both $g_1$ and $g_2$ are continuous on their domain.

27. Therefore, taking the limit $\alpha \to 0^{+}$, it follows that

    $$g_1(0)\le t{g}_2(0)+(1-t)f(\mathbf{y})-\frac{\sigma t(1-t)}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

28. Now $g_1(0)=f(t\mathbf{x}+(1-t)\mathbf{y})$ and $g_2(0)=f(\mathbf{x})$.

29. Thus,

    $$f(t\mathbf{x}+(1-t)\mathbf{y})\le tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{\sigma t(1-t)}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

30. This establishes that $f$ is indeed $\sigma$-strongly convex.

(1) $⟹$ (3)

1. We are given that $f$ is $\sigma$-strongly convex.

2. Let $\mathbf{x},\mathbf{y}\in \mathrm{dom}(\partial f)$.

3. Pick any ${\mathbf{g}}_{\mathbf{x}}\in \partial f(\mathbf{x})$ and ${\mathbf{g}}_{\mathbf{y}}\in \partial f(\mathbf{y})$.

4. Let $t\in [0,1)$ and denote ${\mathbf{x}}_t=t\mathbf{x}+(1-t)\mathbf{y}$.

5. By the hypothesis

   $$f({\mathbf{x}}_t)\le tf(\mathbf{x})+(1-t)f(\mathbf{y})-\frac{\sigma t(1-t)}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

6. This is same as

   $$f({\mathbf{x}}_t)-f(\mathbf{x})\le (1-t)[f(\mathbf{y})-f(\mathbf{x})]-\frac{\sigma t(1-t)}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

7. We can see that $(1-t)\in (0,1]$.

8. Dividing both sides of inequality by $(1-t)$, we obtain

   $$\frac{f({\mathbf{x}}_t)-f(\mathbf{x})}{1-t}\le f(\mathbf{y})-f(\mathbf{x})-\frac{\sigma t}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

9. Since ${\mathbf{g}}_{\mathbf{x}}\in \partial f(\mathbf{x})$, hence by subgradient inequality

   $$f({\mathbf{x}}_t)\ge f(\mathbf{x})+⟨{\mathbf{x}}_t-\mathbf{x},{\mathbf{g}}_{\mathbf{x}}⟩.$$

10. We can rewrite this as

    $$\frac{f({\mathbf{x}}_t)-f(\mathbf{x})}{1-t}\ge \frac{⟨{\mathbf{x}}_t-\mathbf{x},{\mathbf{g}}_{\mathbf{x}}⟩}{1-t}.$$

11. Note that ${\mathbf{x}}_t-\mathbf{x}=(1-t)(\mathbf{y}-\mathbf{x})$.

12. Thus,

    $$\frac{f({\mathbf{x}}_t)-f(\mathbf{x})}{1-t}\ge ⟨\mathbf{y}-\mathbf{x},{\mathbf{g}}_{\mathbf{x}}⟩.$$

13. Thus,

    $$⟨\mathbf{y}-\mathbf{x},{\mathbf{g}}_{\mathbf{x}}⟩\le f(\mathbf{y})-f(\mathbf{x})-\frac{\sigma t}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

14. This inequality holds for every $t\in [0,1)$.

15. Taking the limit $t\to 1^{-}$, we obtain

    $$⟨\mathbf{y}-\mathbf{x},{\mathbf{g}}_{\mathbf{x}}⟩\le f(\mathbf{y})-f(\mathbf{x})-\frac{\sigma }{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

16. An identical reasoning by switching the roles of $\mathbf{x}$ and $\mathbf{y}$, gives us

    $$⟨\mathbf{x}-\mathbf{y},{\mathbf{g}}_{\mathbf{y}}⟩\le f(\mathbf{x})-f(\mathbf{y})-\frac{\sigma }{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2.$$

17. Adding these two inequalities gives us

    $$⟨\mathbf{x}-\mathbf{y},{\mathbf{g}}_{\mathbf{y}}-{\mathbf{g}}_{\mathbf{x}}⟩\le -\sigma \Vert \mathbf{x}-\mathbf{y}{\Vert }^2.$$

18. Multiplying both sides by $-1$ (and switching the inequality accordingly), we get

    $$⟨\mathbf{x}-\mathbf{y},{\mathbf{g}}_{\mathbf{x}}-{\mathbf{g}}_{\mathbf{y}}⟩\ge \sigma \Vert \mathbf{x}-\mathbf{y}{\Vert }^2$$

    as desired.

(3) $⟹$ (2)

1. We are given that (3) is satisfied.

2. Let $\mathbf{x}\in \mathrm{dom}(\partial f)$, $\mathbf{y}\in \mathrm{dom}f$ and $\mathbf{g}\in \partial f(\mathbf{x})$.

3. Pick any $\mathbf{z}\in \mathrm{ri}\mathrm{dom}f$.

4. Pick some $\alpha \in (0,1)$.

5. Define $\tilde{\mathbf{y}}=(1-\alpha )\mathbf{y}+\alpha \mathbf{z}$.

6. By line segment property $\tilde{\mathbf{y}}\in \mathrm{ri}\mathrm{dom}f$.

7. Define ${\mathbf{x}}_t=(1-t)\mathbf{x}+t\tilde{\mathbf{y}}$.

8. Consider the 1D function

   $$\phi (t)=f({\mathbf{x}}_t),\mathrm{\forall }t\in [0,1].$$

9. Pick any $t\in (0,1)$.

10. Then, by line segment principle ${\mathbf{x}}_t\in \mathrm{ri}\mathrm{dom}f$.

11. Due to (Theorem 9.217), $\partial f({\mathbf{x}}_t)\ne \varnothing$ and ${\mathbf{x}}_t\in \mathrm{dom}(\partial f)$.

12. Take some ${\mathbf{g}}_t\in \partial f({\mathbf{x}}_t)$.

13. By subgradient inequality

    $$f(\mathbf{z})\ge f({\mathbf{x}}_t)+⟨\mathbf{z}-{\mathbf{x}}_t,{\mathbf{g}}_t⟩\mathrm{\forall }\mathbf{z}\in \mathbb{V}.$$

14. In particular, for ${\mathbf{x}}_s=(1-s)\mathbf{x}+s\tilde{\mathbf{y}}$, we have

    $$\begin{array}{rl}& f({\mathbf{x}}_s)\ge f({\mathbf{x}}_t)+⟨(1-s)\mathbf{x}+s\tilde{\mathbf{y}}-(1-t)\mathbf{x}-t\tilde{\mathbf{y}},{\mathbf{g}}_t⟩\\ & ⟹\phi (s)\ge \phi (t)+⟨(s-t)(\tilde{\mathbf{y}}-\mathbf{x}),{\mathbf{g}}_t⟩\\ & ⟹\phi (s)\ge \phi (t)+(s-t)⟨\tilde{\mathbf{y}}-\mathbf{x},{\mathbf{g}}_t⟩.\end{array}$$

15. Since this is valid for every $s$, hence $⟨\tilde{\mathbf{y}}-\mathbf{x},{\mathbf{g}}_t⟩\in \partial \phi (t)$.

16. Applying the mean value theorem (Theorem 9.234)

    $$f(\tilde{\mathbf{y}})-f(\mathbf{x})=\phi (1)-\phi (0)={\int }_0^1⟨\tilde{\mathbf{y}}-\mathbf{x},{\mathbf{g}}_t⟩dt.$$

17. Since $\mathbf{g}\in \partial f(\mathbf{x})$ and ${\mathbf{g}}_t\in \partial f({\mathbf{x}}_t)$, hence applying the hypothesis (3), we get

    $$⟨{\mathbf{x}}_t-\mathbf{x},{\mathbf{g}}_t-\mathbf{g}⟩\ge \sigma \Vert {\mathbf{x}}_t-\mathbf{x}{\Vert }^2.$$

18. But ${\mathbf{x}}_t-\mathbf{x}=t(\tilde{\mathbf{y}}-\mathbf{x})$.

19. Hence

    $$t⟨\tilde{\mathbf{y}}-\mathbf{x},{\mathbf{g}}_t-\mathbf{g}⟩\ge \sigma t^2\Vert \tilde{\mathbf{y}}-\mathbf{x}{\Vert }^2.$$

20. This simplifies to

    $$⟨\tilde{\mathbf{y}}-\mathbf{x},{\mathbf{g}}_t⟩\ge ⟨\tilde{\mathbf{y}}-\mathbf{x},\mathbf{g}⟩+\sigma t\Vert \tilde{\mathbf{y}}-\mathbf{x}{\Vert }^2.$$

    Canceling $t$ on both sides doesn’t change the sign of inequality since $t>0$.

21. Applying the inequality to the integral above

    $$f(\tilde{\mathbf{y}})-f(\mathbf{x})\ge {\int }_0^1[⟨\tilde{\mathbf{y}}-\mathbf{x},\mathbf{g}⟩+\sigma t\Vert \tilde{\mathbf{y}}-\mathbf{x}{\Vert }^2]dt.$$

22. Integrating, we get

    $$f(\tilde{\mathbf{y}})-f(\mathbf{x})\ge ⟨\tilde{\mathbf{y}}-\mathbf{x},\mathbf{g}⟩+\frac{\sigma }{2}\Vert \tilde{\mathbf{y}}-\mathbf{x}{\Vert }^2.$$

23. Expanding for $\tilde{\mathbf{y}}$ for any $\alpha \in (0,1)$, we have

    $$f((1-\alpha )\mathbf{y}+\alpha \mathbf{z})\ge f(\mathbf{x})+⟨(1-\alpha )\mathbf{y}+\alpha \mathbf{z}-\mathbf{x},\mathbf{g}⟩+\frac{\sigma }{2}\Vert (1-\alpha )\mathbf{y}+\alpha \mathbf{z}-\mathbf{x}{\Vert }^2.$$

24. The 1D function $g(\alpha )=f((1-\alpha )\mathbf{y}+\alpha \mathbf{z})$ is continuous again due to Theorem 9.173.

25. Taking the limit $\alpha \to 0^{+}$ on both sides, we obtain

    $$f(\mathbf{y})\ge f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathbf{g}⟩+\frac{\sigma }{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2$$

    which is the desired result.

9.18.2.6. Minimization

Theorem 9.272 (Existence and uniqueness of a a minimizer of closed strongly convex function)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper, closed and $\sigma$-strongly convex function with $\sigma >0$. Then,

1. $f$ has a unique minimizer $\mathbf{a}\in \mathrm{dom}f$ such that $f(\mathbf{x})>f(\mathbf{a})$ for every $\mathbf{x}\in \mathrm{dom}f$ and $\mathbf{x}\ne \mathbf{a}$.

2. The increase in the value of $f$ w.r.t. its minimum satisfies

   $$f(\mathbf{x})-f(\mathbf{a})\ge \frac{\sigma }{2}\Vert \mathbf{x}-\mathbf{a}{\Vert }^2$$

   where $\mathbf{a}\in \mathrm{dom}f$ is the unique minimizer of $f$.

Proof. (1) Existence of the minimizer

1. Since $f$ is proper and convex, hence $\mathrm{dom}f$ is nonempty and convex.

2. Since $\mathrm{dom}f$ is nonempty and convex, hence its relative interior is nonempty (Theorem 9.142).

3. Pick $\mathbf{y}\in \mathrm{ri}\mathrm{dom}f$.

4. By Theorem 9.214, $\partial f(\mathbf{y})$ is nonempty.

5. Pick some $\mathbf{g}\in \partial f(\mathbf{y})$.

6. Then, by property 2 of Theorem 9.271,

   $$f(\mathbf{x})\ge f(\mathbf{y})+⟨\mathbf{x}-\mathbf{y},\mathbf{g}⟩+\frac{\sigma }{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2$$

   holds true for every $\mathbf{x}\in \mathbb{V}$.

7. Let $\Vert \cdot {\Vert }_2\triangleq \sqrt{⟨\cdot ,\cdot ⟩}$ denote the Euclidean norm associated with the inner product of the space $\mathbb{V}$. This might be different from the endowed norm $\Vert \cdot \Vert$.

8. Since all norms in a finite dimensional space are equivalent, hence, there exists a constant $C>0$ such that

   $$\Vert \mathbf{z}\Vert \ge \sqrt{C}\Vert \mathbf{z}{\Vert }_2$$

   for every $\mathbf{z}\in \mathbb{V}$.

9. Therefore,

   $$f(\mathbf{x})\ge f(\mathbf{y})+⟨\mathbf{x}-\mathbf{y},\mathbf{g}⟩+\frac{\sigma C}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in \mathbb{V}.$$

10. This in turn is same as

    $$f(\mathbf{x})\ge f(\mathbf{y})-\frac{1}{2C\sigma }\Vert \mathbf{g}{\Vert }_2^2+\frac{C\sigma }{2}{\Vert \mathbf{x}-(\mathbf{y}-\frac{1}{C\sigma }\mathbf{g})\Vert }_2^2\mathrm{\forall }\mathbf{x}\in \mathbb{V}.$$

11. Let $S_t$ denote the sublevel set $\{\mathbf{x}|f(\mathbf{x})\le t\}$.

12. Consider the sublevel set $S_{f(\mathbf{y})}$.

13. Let $\mathbf{x}\in S_{f(\mathbf{y})}$.

14. Then, $f(\mathbf{x})=f(\mathbf{y})-r$ for some $r\ge 0$.

15. But then

    $$f(\mathbf{y})-r\ge f(\mathbf{y})-\frac{1}{2C\sigma }\Vert \mathbf{g}{\Vert }_2^2+\frac{C\sigma }{2}{\Vert \mathbf{x}-(\mathbf{y}-\frac{1}{C\sigma }\mathbf{g})\Vert }_2^2.$$

16. This simplifies to

    $$r\le \frac{1}{2C\sigma }\Vert \mathbf{g}{\Vert }_2^2-\frac{C\sigma }{2}{\Vert \mathbf{x}-(\mathbf{y}-\frac{1}{C\sigma }\mathbf{g})\Vert }_2^2.$$

17. Since $r$ must be nonnegative, hence the R.H.S. must be nonnegative also.

18. Thus, we require that

    $$\frac{1}{2C\sigma }\Vert \mathbf{g}{\Vert }_2^2\ge \frac{C\sigma }{2}{\Vert \mathbf{x}-(\mathbf{y}-\frac{1}{C\sigma }\mathbf{g})\Vert }_2^2.$$

19. This simplifies to

    $${\Vert \mathbf{x}-(\mathbf{y}-\frac{1}{C\sigma }\mathbf{g})\Vert }_2\le \frac{1}{C\sigma }\Vert \mathbf{g}{\Vert }_2.$$

20. In other words, $\mathbf{x}$ must belong to an ${\ell }_2$ closed ball given by

    $$B_{\Vert \cdot {\Vert }_2}[\mathbf{y}-\frac{1}{C\sigma }\mathbf{g},\frac{1}{C\sigma }\Vert \mathbf{g}{\Vert }_2].$$

21. Since this is valid for every $\mathbf{x}\in S_{f(\mathbf{y})}$, hence

    $$S_{f(\mathbf{y})}\subseteq B_{\Vert \cdot {\Vert }_2}[\mathbf{y}-\frac{1}{C\sigma }\mathbf{g},\frac{1}{C\sigma }\Vert \mathbf{g}{\Vert }_2].$$

22. Since $f$ is closed, hence all its sublevel sets are closed.

23. since $S_{f(\mathbf{y})}$ is contained in a ball, hence $S_{f(\mathbf{y})}$ is bounded.

24. Thus, $S_{f(\mathbf{y})}$ is closed and bounded.

25. Since $\mathbb{V}$ is finite dimensional, hence $S_{f(\mathbf{y})}$ is compact.

26. $S_{f(\mathbf{y})}$ is also nonempty since $\mathbf{y}\in S_{f(\mathbf{y})}$.

27. Thus, the problem of minimizing $f$ over $\mathrm{dom}f$ reduces to the problem of minimizing $f$ over the nonempty compact set $S_{f(\mathbf{y})}$.

28. Since $f$ is closed, it is also lower semicontinuous.

29. By Theorem 3.121, $f$ attains a minimum on $S_{f(\mathbf{y})}$ at some point $\mathbf{a}\in S_{f(\mathbf{y})}$.

30. Thus, we have established the existence of a minimizer of $f$ at some $\mathbf{a}\in S_{f(\mathbf{y})}\subseteq \mathrm{dom}f$.

(1) Uniqueness of the minimizer

1. To show the uniqueness, for contradiction, assume that $\mathbf{u}$ and $\mathbf{v}$ are two different minimizers of $f$ with $f(\mathbf{u})=f(\mathbf{v})=p^{\ast }$, the optimal value.

2. Let $\mathbf{w}=\frac{1}{2}\mathbf{u}+\frac{1}{2}\mathbf{v}$.

3. We must have $f(\mathbf{w})\ge p^{\ast }$.

4. By strong convexity of $f$,

   $$f(\mathbf{w})\le \frac{1}{2}f(\mathbf{u})+\frac{1}{2}f(\mathbf{v})-\frac{\sigma }{2}\frac{1}{2}\frac{1}{2}\Vert \mathbf{u}-\mathbf{v}{\Vert }^2=p^{\ast }-\frac{\sigma }{8}\Vert \mathbf{u}-\mathbf{v}{\Vert }^2.$$

5. If $\mathbf{u}\ne \mathbf{v}$, then $f(\mathbf{w})<p^{\ast }$; a contradiction.

6. Hence, the minimizer must be unique.

(2) Increase in value of $f$

1. Let $\mathbf{a}$ be the unique minimizer of $f$.

2. By Fermat’s optimality condition $\mathbf{0}\in \partial f(\mathbf{a})$.

3. Since $f$ is $\sigma$-strongly convex, hence by property (2) in the Theorem 9.271,

   $$f(\mathbf{x})-f(\mathbf{a})\ge ⟨\mathbf{x}-\mathbf{a},\mathbf{0}⟩+\frac{\sigma }{2}\Vert \mathbf{x}-\mathbf{a}{\Vert }^2=\frac{\sigma }{2}\Vert \mathbf{x}-\mathbf{a}{\Vert }^2$$

   holds true for any $\mathbf{x}\in \mathrm{dom}f$.

9.18.3. Smoothness and Strong Convexity

9.18.3.1. The Conjugate Correspondence Theorem

The idea of smoothness and strong convexity is connected. Roughly speaking, a function is strongly convex if and only if its conjugate is smooth.

Theorem 9.273 (Conjugate correspondence theorem)

Let $\sigma >0$. Then

1. If $f:\mathbb{V}\to \mathbb{R}$ is a $\frac{1}{\sigma }$-smooth convex function, then $f^{\ast }$ is $\sigma$-strongly convex w.r.t. the dual norm $\Vert \cdot {\Vert }_{\ast }$.

2. If $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ is a proper, closed $\sigma$-strongly convex function, then $f^{\ast }:{\mathbb{V}}^{\ast }\to \mathbb{R}$ is $\frac{1}{\sigma }$-smooth.

Proof. (1) Smooth convex to strongly convex conjugate

1. We are given that $f:\mathbb{V}\to \mathbb{R}$ is a $\frac{1}{\sigma }$-smooth convex function.

2. Due to Theorem 9.239, $f^{\ast }$ is closed and convex.

3. Since $f$ is proper and convex, hence due to Theorem 9.240, $f^{\ast }$ is proper.

4. Thus $f^{\ast }$ is a proper, closed and convex function.

5. Pick any ${\mathbf{y}}_1,{\mathbf{y}}_2\in \mathrm{dom}(\partial f^{\ast })$.

6. Let ${\mathbf{v}}_1\in \partial f^{\ast }({\mathbf{y}}_1)$ and ${\mathbf{v}}_2\in \partial f^{\ast }({\mathbf{y}}_2)$.

7. Since $f$ is proper and convex, hence by conjugate subgradient theorem (Theorem 9.246)

   $${\mathbf{y}}_1\in \partial f({\mathbf{v}}_1)\text{ and }{\mathbf{y}}_2\in \partial f({\mathbf{v}}_2).$$

8. Since $f$ is smooth, hence it is differentiable. Hence due to Theorem 9.220,

   $${\mathbf{y}}_1=\mathrm{\nabla }f({\mathbf{v}}_1)\text{ and }{\mathbf{y}}_2=\mathrm{\nabla }f({\mathbf{v}}_2).$$

9. Following characterization of smoothness (Theorem 9.265), by its property 4,

   $$⟨{\mathbf{v}}_1-{\mathbf{v}}_2,{\mathbf{y}}_1-{\mathbf{y}}_2⟩\ge \sigma \Vert {\mathbf{y}}_1-{\mathbf{y}}_2{\Vert }_{\ast }^2.$$

10. Since the last inequality holds for any ${\mathbf{y}}_1,{\mathbf{y}}_2\in \mathrm{dom}(\partial f^{\ast })$ and any ${\mathbf{v}}_1\in \partial f^{\ast }({\mathbf{y}}_1),{\mathbf{v}}_2\in \partial f^{\ast }({\mathbf{v}}_2)$, hence following the first order characterization of strong convexity in Theorem 9.271, $f^{\ast }$ is a $\sigma$-strongly convex function.

(2) Strongly convex to smooth conjugate

1. We are given that $f$ is proper, closed and $\sigma$-strongly convex.

2. Pick any $\mathbf{y}\in {\mathbb{V}}^{\ast }$.

3. The conjugate is given by

   $$f^{\ast }(\mathbf{y})=\underset{\mathbf{x}\in \mathbb{V}}{sup}\{⟨\mathbf{x},\mathbf{y}⟩-f(\mathbf{y})\}.$$

4. Define $g(\mathbf{x})=f(\mathbf{x})-⟨\mathbf{x},\mathbf{y}⟩$.

5. We can see that

   $$f^{\ast }(\mathbf{y})=-\underset{\mathbf{x}\in \mathbb{V}}{inf}g(\mathbf{x}).$$

6. Due to the sum rule (Theorem 9.270), $g$ is $\sigma$-strongly convex.

7. Due to Theorem 9.272, $g$ has a unique minimizer.

8. Hence $f^{\ast }(\mathbf{y})$ is finite.

9. Since this is valid for any $\mathbf{y}\in {\mathbb{V}}^{\ast }$, hence $\mathrm{dom}{f}^{\ast }={\mathbb{V}}^{\ast }$.

10. This justifies the signature for $f^{\ast }$ as $f^{\ast }:{\mathbb{V}}^{\ast }\to \mathbb{R}$ being real valued.

11. Let’s continue with any $\mathbf{y}$.

12. Since $\mathrm{dom}{f}^{\ast }={\mathbb{V}}^{\ast }$, hence $\mathbf{y}\in \mathrm{int}\mathrm{dom}{f}^{\ast }$.

13. Now, by the second formulation of conjugate subgradient theorem (Corollary 9.26),

    $$\partial f^{\ast }(\mathbf{y})=\arg {\max }_{\mathbf{x}\in \mathbb{V}}\{⟨\mathbf{x},\mathbf{y}⟩-f(\mathbf{x})\}.$$

14. We can see that

    $$\partial f^{\ast }(\mathbf{y})=-\arg {\min }_{\mathbf{x}\in \mathbb{V}}g(\mathbf{x}).$$

15. Since $g$ has a unique minimizer, hence $\partial f^{\ast }(\mathbf{y})$ is a singleton.

16. Due to Theorem 9.220, $f^{\ast }$ is differentiable at $\mathbf{y}$.

17. Since $\mathbf{y}$ is arbitrary, hence $f^{\ast }$ is differentiable over entire ${\mathbb{V}}^{\ast }$.

18. We now pickup two points ${\mathbf{y}}_1,{\mathbf{y}}_2\in {\mathbb{V}}^{\ast }$ and denote ${\mathbf{v}}_1=\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_1),{\mathbf{v}}_2=\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_2)$.

19. By conjugate subgradient theorem (Theorem 9.246), this is equivalent to ${\mathbf{y}}_1\in \partial f({\mathbf{v}}_1)$ and ${\mathbf{y}}_2\in \partial f({\mathbf{v}}_2)$.

20. Following the first order characterization of strong convexity in Theorem 9.271,

    $$⟨{\mathbf{v}}_1-{\mathbf{v}}_2,{\mathbf{y}}_1-{\mathbf{y}}_2⟩\ge \sigma \Vert {\mathbf{v}}_1-{\mathbf{v}}_2{\Vert }^2.$$

21. In other words

    $$⟨\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_1)-\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_2),{\mathbf{y}}_1-{\mathbf{y}}_2⟩\ge \sigma \Vert \mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_1)-\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_2){\Vert }^2.$$

22. By generalized Cauchy Schwartz inequality (Theorem 4.108)

    $$⟨\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_1)-\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_2),{\mathbf{y}}_1-{\mathbf{y}}_2⟩\le \Vert \mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_1)-\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_2)\Vert \Vert {\mathbf{y}}_1-{\mathbf{y}}_2{\Vert }_{\ast }.$$

23. Thus the previous inequality simplifies to

    $$\Vert \mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_1)-\mathrm{\nabla }{f}^{\ast }({\mathbf{y}}_2)\Vert \le \frac{1}{\sigma }\Vert {\mathbf{y}}_1-{\mathbf{y}}_2{\Vert }_{\ast }.$$

24. This establishes that $f^{\ast }$ is $\frac{1}{\sigma }$-smooth.

9.18.4. Examples

Example 9.84 (Smoothness of $\sqrt{1+|\cdot {|}_2^2}$)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by

$$f(\mathbf{x})=\sqrt{1+\Vert \mathbf{x}{\Vert }_2^2}.$$

$f$ is 1-smooth w.r.t. the ${\ell }_2$-norm.

1. Note that for any $\mathbf{x}\in {\mathbb{R}}^n$, the gradient is given by

   $$\mathrm{\nabla }f(\mathbf{x})=\frac{\mathbf{x}}{\sqrt{1+\Vert \mathbf{x}{\Vert }_2^2}}.$$

2. The Hessian is given by

   $${\mathrm{\nabla }}^f(\mathbf{x})=\frac{\mathbf{I}}{\sqrt{1+\Vert \mathbf{x}{\Vert }_2^2}}-\frac{\mathbf{x}{\mathbf{x}}^T}{(1+\Vert \mathbf{x}{\Vert }_2^2{)}^{\frac{3}{2}}}⪯\frac{\mathbf{I}}{\sqrt{1+\Vert \mathbf{x}{\Vert }_2^2}}⪯\mathbf{I}.$$

3. Therefore, ${\lambda }_{max}({\mathrm{\nabla }}^{2}f(\mathbf{x}))\le 1$ for every $\mathbf{x}\in {\mathbb{R}}^n$.

4. Hence, by Corollary 9.27, $f$ is 1-smooth w.r.t. the ${\ell }_2$-norm.

9.18.4.1. Log-Sum-Exp

Example 9.85 (Smoothness of log-sum-exp)

Consider the log-sum-exp function $f:{\mathbb{R}}^n\to \mathbb{R}$ given by

$$f(\mathbf{x})=\ln \left(\sum _{i=1}^n{e}^{x_i}\right).$$

$f$ is 1-smooth w.r.t. ${\ell }_2$ and ${\ell }_{\mathrm{\infty }}$ norms.

Smoothness w.r.t. ${\ell }_2$ norm

1. The partial derivatives of $f$ are

   $$\frac{\partial f}{\partial x_i}(\mathbf{x})=\frac{e^{x_i}}{\sum _{k=1}^n{e}^{x_k}}.$$

2. The second order partial derivatives are

   $$\begin{array}{r}\frac{{\partial }^{2}f}{\partial x_i\partial x_j}(\mathbf{x})=\{\begin{array}{ll}-\frac{e^{x_i}{e}^{x_j}}{{\left(\sum _{k=1}^n{e}^{x_k}\right)}^2},& i\ne j;\\ -\frac{e^{x_i}{e}^{x_i}}{{\left(\sum _{k=1}^n{e}^{x_k}\right)}^2}+\frac{e^{x_i}}{\sum _{k=1}^n{e}^{x_k}},& i=j.\end{array}\end{array}$$

3. The Hessian can be written as

   $${\mathrm{\nabla }}^{2}f(\mathbf{x})=\mathrm{diag}(\mathbf{w})-\mathbf{w}{\mathbf{w}}^T$$

   where $w_i=\frac{e^{x_i}}{\sum _{k=1}^n{e}^{x_k}}$.

4. We can now see that

   $${\mathrm{\nabla }}^{2}f(\mathbf{x})=\mathrm{diag}(\mathbf{w})-\mathbf{w}{\mathbf{w}}^T⪯\mathrm{diag}(\mathbf{w})⪯\mathbf{I}.$$

5. Hence ${\lambda }_{max}({\mathrm{\nabla }}^{2}f(\mathbf{x}))\le 1$ for every $\mathbf{x}\in {\mathbb{R}}^n$.

6. Hence, by Corollary 9.27, $f$ is 1-smooth w.r.t. the ${\ell }_2$-norm.

Smoothness w.r.t. ${\ell }_{\mathrm{\infty }}$ norm

1. We first show that for any $\mathbf{v}\in \mathbb{V}$

   $${\mathbf{v}}^T{\mathrm{\nabla }}^{2}f(\mathbf{x})\mathbf{v}\le \Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}^2.$$

2. To see this, we expand the L.H.S. as

   $$\begin{array}{rl}{\mathbf{v}}^T{\mathrm{\nabla }}^{2}f(\mathbf{x})\mathbf{v}& ={\mathbf{v}}^T(\mathrm{diag}(\mathbf{w})-\mathbf{w}{\mathbf{w}}^T)\mathbf{v}\\ & ={\mathbf{v}}^T\mathrm{diag}(\mathbf{w})\mathbf{v}-({\mathbf{w}}^T\mathbf{v}{)}^2\\ & \le {\mathbf{v}}^T\mathrm{diag}(\mathbf{w})\mathbf{v}\\ & =\sum _{i=1}^n{w}_i{v}_i^2\\ & \le \Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}^2\sum _{i=1}^n{w}_i\\ & =\Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}^2.\end{array}$$

3. Since $f$ is twice differentiable over ${\mathbb{R}}^n$, hence by linear approximation theorem (Theorem 5.5), for any $\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$, there exists $\mathbf{z}\in [\mathbf{x},\mathbf{y}]$ such that

   $$f(\mathbf{y})-f(\mathbf{x})=\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{1}{2}(\mathbf{y}-\mathbf{x}{)}^T{\mathrm{\nabla }}^{2}f(\mathbf{z})(\mathbf{y}-\mathbf{x}).$$

4. Let $\mathbf{v}=\mathbf{y}-\mathbf{x}$.

5. Then from above,

   $$(\mathbf{y}-\mathbf{x}{)}^T{\mathrm{\nabla }}^{2}f(\mathbf{z})(\mathbf{y}-\mathbf{x})\le \Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}^2.$$

6. Putting this back in the approximation, we have

   $$f(\mathbf{y})\le f(\mathbf{x})+\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{1}{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }_{\mathrm{\infty }}^2.$$

7. Following characterization of smoothness (Theorem 9.265), $f$ is indeed 1-smooth w.r.t. the ${\ell }_{\mathrm{\infty }}$-norm.

9.18.4.2. Negative Entropy

Example 9.86 (Strong convexity of negative entropy over the unit simplex)

Let $f:{\mathbb{R}}^n\to (-\mathrm{\infty },\mathrm{\infty }]$ be given by:

$$\begin{array}{r}f(\mathbf{x})\triangleq \{\begin{array}{ll}\sum _{i=1}^n{x}_i\ln x_i& \mathbf{x}\in {\mathrm{\Delta }}_n\\ \mathrm{\infty }& \text{ otherwise }\end{array}.\end{array}$$

$f$ is 1-strongly convex for both ${\ell }_1$ and ${\ell }_2$ norms.

1. By Theorem 9.257, its conjugate is given by

   $$f^{\ast }(\mathbf{y})=\ln \left(\sum _{j=1}^n{e}^{y_j}\right)$$

   which is the log sum exp function.

2. By Example 9.85, the log-sum-exp function is 1-smooth w.r.t. both ${\ell }_2$ and ${\ell }_{\mathrm{\infty }}$ norms.

3. Hence by conjugate correspondence theorem Theorem 9.273, $f$ is 1-strongly convex for both ${\ell }_1$ and ${\ell }_2$ norms.