Chapter 3: Convex Functions

Convex functions are the fundamental objects of study in convex optimization. This chapter develops the definition of convex functions, their properties, various characterizations (first-order, second-order, and gradient monotonicity), as well as operations that preserve convexity and related geometric concepts.

---

3.1 Operations That Preserve Convexity of Sets

Before studying convex functions per se, it is useful to review how convexity of sets can be established through operations that preserve it. Given a set $C\subseteq {\mathbb{R}}^n$, there are three practical approaches to verifying convexity:

1. Apply the definition directly:

   $$x_1,x_2\in C,0\le \theta \le 1⟹\theta x_1+(1-\theta )x_2\in C$$

2. Show that $C$ is obtained from simple convex sets (hyperplanes, halfspaces, norm balls, etc.) by operations that preserve convexity:

   • Intersection
   • Affine function
   • Perspective function
   • Linear-fractional function

3. Show that $C$ is a sublevel set of a convex function (discussed later).

3.1.1 Intersection

Property (Intersection of Convex Sets). The intersection of any number (including infinite) of convex sets is convex: if each $C_i$ is convex, then $\bigcap _{i\in I}{C}_i$ is convex.

Examples:

• Affine space: An affine space defined by linear equalities can be expressed as an intersection of hyperplanes:

  $$\{x:Ax=b\}=\bigcap _{i=1}^m\{x:a_i^{\mathrm{\top }}x=b_i\}$$

  Each equality constraint is the intersection of two halfspaces $\{x:a_i^{\mathrm{\top }}x\le b_i\}$ and $\{x:a_i^{\mathrm{\top }}x\ge b_i\}$.

• ${\ell }_{\mathrm{\infty }}$-ball:

  $$B_{\mathrm{\infty }}=\{x:\parallel x{\parallel }_{\mathrm{\infty }}\le 1\}=\bigcap _{i=1}^n\{x:-1\le x_i\le 1\}$$

  Each constraint is a halfspace, so the intersection is convex.

• PSD cone: The cone of positive semidefinite matrices

  $${\mathbb{S}}_{+}^n=\{X⪰0\}=\bigcap _{v\in {\mathbb{R}}^n}\{X:v^{\mathrm{\top }}Xv\ge 0\}$$

  is the intersection of infinitely many halfspaces.

3.1.2 Affine Mapping

Property (Affine Image). If $C$ is convex and $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$, then the image under an affine map

$$\{y=Ax+b:x\in C\}$$

is convex.

Example (Scaling and Translation): Scaling and translating a convex set preserves convexity:

$$C=\{x:\parallel x{\parallel }_2\le 1\}⟹AC+b=\{y:y=Ax+b,\parallel x{\parallel }_2\le 1\}$$

Interpretation: Linear transformations do not "bend" the set.

3.1.3 Inverse Affine Mapping

Property (Affine Preimage). If $S\subset {\mathbb{R}}^n$ is convex and $f:{\mathbb{R}}^m\to {\mathbb{R}}^n$ is affine, the preimage is also convex:

$$f^{-1}(S)=\{x\in {\mathbb{R}}^m:f(x)\in S\}$$

Application: Linear Matrix Inequality (LMI). Consider

$$F(x)=F_0+\sum _{i=1}^n{x}_i{F}_i⪰0$$

The set of positive semidefinite matrices ${\mathbb{S}}_{+}^m=\{X\in {\mathbb{S}}^m:X⪰0\}$ is convex. The mapping $x\mapsto F(x)$ is affine. Therefore, the solution set

$$\{x:F(x)⪰0\}=F^{-1}({\mathbb{S}}_{+}^m)$$

is convex by the affine preimage property.

---

3.2 Fundamental Concepts in Set Topology

We briefly review essential topological concepts that are foundational in convex analysis.

• A point $x\in {\mathbb{R}}^n$ is an $n$-tuple $(x_1,\dots ,x_n)$.
• A set $S\subseteq {\mathbb{R}}^n$ is a collection of points.
• The open ball (neighborhood) centered at $x$ with radius $ϵ$:$$B_{ϵ}(x)=\{y\in {\mathbb{R}}^n:\parallel y-x\parallel <ϵ\}$$

3.2.1 Open and Closed Sets

Open Set. Every point has a neighborhood contained in the set:

$$\mathrm{\forall }x\in S,\mathrm{\exists }ϵ>0:B_{ϵ}(x)\subset S$$

Example: $(0,1)$.

Closed Set. Contains all its limit points; its complement is open. Example: $[0,1]$.

3.2.2 Interior and Relative Interior

Interior. $\mathrm{int}(S)=\{x\in S:\mathrm{\exists }ϵ>0,B_{ϵ}(x)\subset S\}$ Points with a neighborhood contained in $S$. Example: $\mathrm{int}([0,1])=(0,1)$.

Relative Interior (relint). If $S$ lies in an affine subspace $A$, then $x\in S$ is a relative interior point if

$$B_{ϵ}(x)\cap A\subseteq S$$

for some $ϵ>0$. The set of all such points is $\mathrm{relint}(S)$.

Example: The line segment $[0,1]$ in ${\mathbb{R}}^2$ has empty interior, but its relative interior is $(0,1)$ within the line it spans.

3.2.3 Limit Points and Closure

Limit Point. Every neighborhood contains other points from the set:

$$\mathrm{\forall }ϵ>0:B_{ϵ}(x)\cap (S\setminus \{x\})\ne \varnothing$$

Points arbitrarily close to $x$ are in $S$.

Closure. $\mathrm{cl}(S)$ is $S$ together with all its limit points; it is the smallest closed set containing $S$.

$$\mathrm{cl}((0,1))=[0,1]$$

3.2.4 Boundary

Boundary. $\partial S=\mathrm{cl}(S)\setminus \mathrm{int}(S)$

Every neighborhood contains points from both $S$ and its complement.

Example: $S=(0,1]$

• $\mathrm{cl}(S)=[0,1]$, $\mathrm{int}(S)=(0,1)$, $\partial S=\{0,1\}$

Key Relationships:

• $\mathrm{cl}(S)=\mathrm{int}(S)\cup \partial S$
• $\mathrm{int}(S)\cap \partial S=\varnothing$
• $\mathrm{int}(S)\subseteq S\subseteq \mathrm{cl}(S)$

---

3.3 Definition of Convex Functions

Definition (Convex Function). A function $f:C\to \mathbb{R}$ defined on a convex set $C\subseteq {\mathbb{R}}^n$ is called convex if

$$\begin{array}{}\text{(3.1)}& f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)\end{array}$$

for all $x,y\in C$ and all $\theta \in [0,1]$.

Definition (Strictly Convex). $f$ is strictly convex if the inequality is strict whenever $x\ne y$ and $\theta \in (0,1)$:

$$\begin{array}{}\text{(3.2)}& f(\theta x+(1-\theta )y)<\theta f(x)+(1-\theta )f(y)\end{array}$$

Definition (Concave Function). $f$ is concave if $-f$ is convex, i.e.,

$$\begin{array}{}\text{(3.3)}& f(\theta x+(1-\theta )y)\ge \theta f(x)+(1-\theta )f(y)\end{array}$$

Geometric meaning: For a convex function $f$, the graph lies below the chord connecting any two points. For a concave function, the graph lies above the chord.

Note: Linear (affine) functions are both convex and concave, but neither strictly convex nor strictly concave.

---

3.4 Common Examples of Convex Functions

Univariate examples:

• $f(x)=ax+b$ (affine)
• $f(x)=x^2$, $f(x)=e^{ax}$, $f(x)=|x{|}^p$ for $p\ge 1$
• $f(x)=-\log x$ on $(0,\mathrm{\infty })$

Multivariate examples:

• $f(x)=a^{\mathrm{\top }}x+b$ (affine)
• $f(x)=x^{\mathrm{\top }}Px$ with $P⪰0$ (quadratic)
• $f(x)=\parallel x\parallel$ (any norm)
• $f(x)=max\{x_1,\dots ,x_n\}$
• $f(x)=\log \left(\sum _i{e}^{x_i}\right)$ (log-sum-exp)

---

3.5 Convexity via Restriction to Lines

Theorem (Restriction to Lines). A function $f:C\to \mathbb{R}$ with $\mathrm{dom}f=C\subseteq {\mathbb{R}}^n$ is convex if and only if for every $z,v\in {\mathbb{R}}^n$ with $\{z+tv:t\in \mathbb{R}\}\cap C\ne \varnothing$, the one-dimensional function

$$\varphi (t)=f(z+tv)$$

is convex on its domain $\{t:z+tv\in C\}$.

Intuition: This theorem reduces multivariate convexity to one-dimensional verification.

Examples:

• $f(x,y)=x^2+y^2⟶g(t)=(z_1+t{v}_1{)}^2+(z_2+t{v}_2{)}^2$ (quadratic in $t$)
• $f(X)=-\log detX$ with $\mathrm{dom}f={\mathbb{S}}_{++}^n$

---

Proposition. Let $C\subset {\mathbb{R}}^n$ be convex and $f:C\to \mathbb{R}$. Then $f$ is convex if and only if for every line $L=\{x+tv:t\in \mathbb{R}\}$ meeting $C$, the restriction $\varphi (t)=f(x+tv)$ is convex on $\{t:x+tv\in C\}$.

Proof.

$(\Rightarrow )$ If $f$ is convex, then for any $t_1,t_2$ with $x+t_{1}v,x+t_{2}v\in C$ and $\lambda \in [0,1]$,

$$f(\lambda (x+t_{1}v)+(1-\lambda )(x+t_{2}v))\le \lambda f(x+t_{1}v)+(1-\lambda )f(x+t_{2}v),$$

which is the same as

$$\varphi (\lambda t_1+(1-\lambda )t_2)\le \lambda \varphi (t_1)+(1-\lambda )\varphi (t_2),$$

so $\varphi$ is convex.

$(\Leftarrow )$ Conversely, let $x,y\in C$ and $\theta \in [0,1]$. Define $\varphi (t)=f(y+t(x-y))$. Then

$$f(\theta x+(1-\theta )y)=\varphi (\theta )\le \theta \varphi (1)+(1-\theta )\varphi (0)=\theta f(x)+(1-\theta )f(y),$$

so $f$ is convex. $◻$

---

3.6 Epigraph and Sublevel Sets

3.6.1 Epigraph

Definition (Epigraph). For a function $f:{\mathbb{R}}^n\to \mathbb{R}$, the epigraph of $f$ is the set

$$\mathrm{epi}f=\{(x,t)\in {\mathbb{R}}^{n+1}:f(x)\le t\}$$

Geometric meaning: The epigraph is the region on or above the graph of $f$.

Key Property. $f$ is convex $⟺$ $\mathrm{epi}f$ is a convex set.

Proposition. Let $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\mathrm{\infty }\}$ and $\mathrm{epi}f=\{(x,t)\in {\mathbb{R}}^{n+1}:f(x)\le t\}$. Then $f$ is convex on its domain if and only if $\mathrm{epi}f$ is a convex set.

Proof.

$(\Rightarrow )$ Assume $f$ is convex. Take $(x_1,t_1),(x_2,t_2)\in \mathrm{epi}f$ so $f(x_i)\le t_i$. For any $\theta \in [0,1]$, set $\overline{x}=\theta x_1+(1-\theta )x_2$ and $\overline{t}=\theta t_1+(1-\theta )t_2$. By convexity of $f$,

$$f(\overline{x})\le \theta f(x_1)+(1-\theta )f(x_2)\le \theta t_1+(1-\theta )t_2=\overline{t},$$

hence $(\overline{x},\overline{t})\in \mathrm{epi}f$. Thus $\mathrm{epi}f$ is convex.

$(\Leftarrow )$ Conversely, assume $\mathrm{epi}f$ is convex. For any $x_1,x_2\in \mathrm{dom}f$ and $\theta \in [0,1]$, the points $(x_i,f(x_i))\in \mathrm{epi}f$, so their convex combination $(\overline{x},\overline{t})$ with $\overline{x}=\theta x_1+(1-\theta )x_2$ and $\overline{t}=\theta f(x_1)+(1-\theta )f(x_2)$ lies in $\mathrm{epi}f$. Therefore $f(\overline{x})\le \overline{t}$, i.e.

$$f(\theta x_1+(1-\theta )x_2)\le \theta f(x_1)+(1-\theta )f(x_2),$$

so $f$ is convex. $◻$

3.6.2 Sublevel Sets

Definition (Sublevel Set). For $f:{\mathbb{R}}^n\to \mathbb{R}$ and $\alpha \in \mathbb{R}$, the $\alpha$-sublevel set is

$$S_{\alpha }=\{x\in \mathrm{dom}(f):f(x)\le \alpha \}$$

the set of points where $f$ takes values $\le \alpha$.

Key Property. If $f$ is convex, then all sublevel sets $S_{\alpha }$ are convex.

Warning: The converse is not true. For example, $f(x)=x^3$ has convex sublevel sets but is not convex.

Examples:

• $f(x)=x^2$: $S_{\alpha }=[-\sqrt{\alpha },\sqrt{\alpha }]$ (convex intervals)
• $f(x)=x^3$: $S_{\alpha }=(-\mathrm{\infty },\sqrt[3]{\alpha }]$ (convex intervals, but $f$ is not convex)

---

3.7 Jensen's Inequality

Theorem (Jensen's Inequality — Discrete Form). If $f$ is convex and ${\theta }_i\ge 0$ with $\sum _{i=1}^k{\theta }_i=1$, then

$$\begin{array}{}\text{(3.4)}& f\left(\sum _{i=1}^k{\theta }_i{x}_i\right)\le \sum _{i=1}^k{\theta }_{i}f(x_i)\end{array}$$

Integral Form. For convex $f$ and a probability measure $p$:

$$f(\int xp(x)dx)\le \int f(x)p(x)dx$$

Expectation Form. For convex $f$ and a random variable $X$:

$$f(\mathbb{E}[X])\le \mathbb{E}[f(X)]$$

---

3.8 First-Order Condition for Convexity

3.8.1 Gradient and Differentiability

Precondition: $f$ is differentiable if the gradient

$$\mathrm{\nabla }f(x)={(\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\dots ,\frac{\partial f(x)}{\partial x_n})}^{\mathrm{\top }}$$

exists at each $x\in \mathrm{dom}f$.

Theorem (First-Order Condition). A differentiable function $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex if and only if for all $x,y\in \mathrm{dom}f$:

$$\begin{array}{}\text{(3.5)}& f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)\end{array}$$

Implication: If $\mathrm{\nabla }f(x^{\ast })=0$, then $x^{\ast }$ is a global minimum.

Example: $f(x)=x^2$, $\mathrm{\nabla }f(x)=2x$:

$$f(y)=y^2\ge x^2+2x(y-x)$$

3.8.2 Proof of Equivalence

Direction 1: Basic convexity $\Rightarrow$ first-order condition.

Assume $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex and differentiable. For any $x,y$ and $\theta \in (0,1]$:

$$f(x+\theta (y-x))\le (1-\theta )f(x)+\theta f(y).$$

Subtract $f(x)$ and divide by $\theta >0$:

$$\frac{f(x+\theta (y-x))-f(x)}{\theta }\le f(y)-f(x).$$

Take $\theta \to 0$. Differentiability implies:

$$\underset{\theta \to 0}{lim}\frac{f(x+\theta (y-x))-f(x)}{\theta }=\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x).$$

Hence:

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x).$$

Direction 2: First-order condition $\Rightarrow$ basic convexity.

Assume for all $x,y$:

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x).$$

Let $z=\theta x+(1-\theta )y$ with $\theta \in [0,1]$. Apply the condition twice:

$$f(x)\ge f(z)+\mathrm{\nabla }f(z{)}^{\mathrm{\top }}(x-z),$$$$f(y)\ge f(z)+\mathrm{\nabla }f(z{)}^{\mathrm{\top }}(y-z).$$

Multiply the two inequalities by $\theta$ and $1-\theta$ respectively and add:

$$\theta f(x)+(1-\theta )f(y)\ge f(z)+\mathrm{\nabla }f(z{)}^{\mathrm{\top }}(\theta x+(1-\theta )y-z).$$

Since $z=\theta x+(1-\theta )y$, we have:

$$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y).$$

---

3.9 Gradient Monotonicity

Definition (Monotone Gradient). A differentiable function $f:{\mathbb{R}}^n\to \mathbb{R}$ has a monotone gradient if for all $x,y\in \mathrm{dom}f$:

$$\begin{array}{}\text{(3.6)}& ⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge 0\end{array}$$

Connection to Convexity:

• If $f$ is convex, its gradient is monotone.
• Conversely, if $\mathrm{\nabla }f$ is monotone, $f$ is convex.

Example: $f(x)=x^{\mathrm{\top }}Qx$ with $Q⪰0$:

$$\mathrm{\nabla }f(x)=2Qx,⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩=2(x-y{)}^{\mathrm{\top }}Q(x-y)\ge 0$$

3.9.1 Proof of Equivalence between First-Order Condition and Gradient Monotonicity

Direction 1: First-order condition $\Rightarrow$ Gradient Monotonicity.

Assume $f:D\to \mathbb{R}$ is differentiable and satisfies the first-order condition:

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x),\mathrm{\forall }x,y\in D.$$

Write this inequality twice, swapping $x$ and $y$:

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x),$$$$f(x)\ge f(y)+\mathrm{\nabla }f(y{)}^{\mathrm{\top }}(x-y).$$

Adding the two inequalities yields:

$$0\ge \mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)+\mathrm{\nabla }f(y{)}^{\mathrm{\top }}(x-y),$$

which simplifies to

$$⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge 0.$$

Direction 2: Gradient Monotonicity $\Rightarrow$ First-order condition.

Assume $f$ is differentiable and satisfies gradient monotonicity:

$$(\mathrm{\nabla }f(y)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)\ge 0.$$

For any $x,y\in D$, by the Fundamental Theorem of Calculus along the line segment:

$$f(y)-f(x)={\int }_0^1\frac{d}{dt}f(x+t(y-x))dt={\int }_0^1\mathrm{\nabla }f(x+t(y-x){)}^{\mathrm{\top }}(y-x)dt.$$

Subtract the tangent at $x$:

$$f(y)-f(x)-\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)={\int }_0^1(\mathrm{\nabla }f(x+t(y-x))-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)dt\ge 0.$$

This gives the first-order condition:

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x).$$

---

3.10 Second-Order Condition for Convexity

Precondition: $f$ is twice-differentiable if $\mathrm{dom}f$ is open and the Hessian

$${\mathrm{\nabla }}^{2}f(x{)}_{ij}=\frac{{\partial }^{2}f(x)}{\partial x_i\partial x_j},i,j=1,\dots ,n,$$

exists at each $x\in \mathrm{dom}f$.

Theorem (Second-Order Condition). A twice-differentiable function $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex if and only if its Hessian is positive semidefinite for all $x\in \mathrm{dom}f$:

$$\begin{array}{}\text{(3.7)}& {\mathrm{\nabla }}^{2}f(x)⪰0\end{array}$$

Example: $f(x)=x^{\mathrm{\top }}Qx$ with $Q⪰0$:

$$\mathrm{\nabla }f(x)=2Qx,{\mathrm{\nabla }}^{2}f(x)=2Q⪰0$$

3.10.1 Proof of Equivalence between Gradient Monotonicity and Second-Order Condition

Direction 1: Gradient Monotonicity $\Rightarrow$ Hessian PSD.

Assume $(\mathrm{\nabla }f(y)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)\ge 0$ for all $x,y\in D$. Consider an infinitesimal perturbation along direction $d$: $y=x+ϵd$, $ϵ>0$. Gradient monotonicity implies:

$$(\mathrm{\nabla }f(x+ϵd)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(ϵd)\ge 0⟹\frac{(\mathrm{\nabla }f(x+ϵd)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}d}{ϵ}\ge 0.$$

Take the limit as $ϵ\to 0$:

$$d^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)d\ge 0\mathrm{\forall }d\in {\mathbb{R}}^n.$$

Direction 2: Hessian PSD $\Rightarrow$ Gradient Monotonicity.

Assume $f:D\to \mathbb{R}$ is twice differentiable and ${\mathrm{\nabla }}^{2}f(x)⪰0$ for all $x\in D$. For any $x,y\in D$, consider the line segment $x+t(y-x)$, $t\in [0,1]$:

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

Take inner product with $y-x$:

$$(\mathrm{\nabla }f(y)-\mathrm{\nabla }f(x){)}^{\mathrm{\top }}(y-x)={\int }_0^1(y-x{)}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x+t(y-x))(y-x)dt\ge 0.$$

---

3.11 Chain of Equivalences

For twice-differentiable functions, the following four statements are equivalent characterizations of convexity:

   Convexity
f(θx + (1−θ)y) ≤ θf(x) + (1−θ)f(y)
        ⇕
 First-order Condition                  Gradient Monotonicity
f(y) ≥ f(x) + ∇f(x)ᵀ(y−x)    ⇔    ⟨∇f(x)−∇f(y), x−y⟩ ≥ 0
        ⇕
 Second-order Condition
    ∇²f(x) ⪰ 0

In summary:

1. Convexity (Definition): $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$
2. First-order Condition: $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)$
3. Gradient Monotonicity: $⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge 0$
4. Second-order Condition: ${\mathrm{\nabla }}^{2}f(x)⪰0$

Each provides a different practical tool for verifying or exploiting convexity in analysis and algorithm design.

---

3.12 Smooth and Strongly Convex Functions

Beyond mere convexity, many optimization algorithms rely on stronger structural assumptions—smoothness and strong convexity—to obtain quantitative convergence guarantees. This section develops L-smoothness (Lipschitz gradient) and m-strong convexity, their equivalent characterizations, and the convergence rates of gradient descent under these conditions.

3.12.1 L-Smooth Functions

Definition (L-smooth function). A differentiable function $f:{\mathbb{R}}^n\to \mathbb{R}$ is called L-smooth (or has an L-Lipschitz continuous gradient) for some $L>0$ if for all $x,y\in {\mathbb{R}}^n$,

$$\begin{array}{}\text{(3.8)}& \parallel \mathrm{\nabla }f(x)-\mathrm{\nabla }f(y)\parallel \le L\parallel x-y\parallel .\end{array}$$

Smoothness bounds how fast the gradient can change. Unlike convexity, it does not guarantee that stationary points are global minima; it only guarantees a quadratic upper bound on the function.

---

Chain of Equivalences. For a twice-differentiable function $f$, the following four statements are equivalent characterizations of L-smoothness:

$$\begin{array}{rl}\text{(I)}& \parallel \mathrm{\nabla }f(x)-\mathrm{\nabla }f(y)\parallel \le L\parallel x-y\parallel \text{(Lipschitz gradient)}\\ \text{(II)}& g(x)=\frac{L}{2}\parallel x{\parallel }^2-f(x)\text{ is convex}\\ \text{(III)}& f(y)\le f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{L}{2}\parallel y-x{\parallel }^2\text{(Descent Lemma)}\\ \text{(IV)}& {\mathrm{\nabla }}^{2}f(x)⪯LI\text{(Hessian bound)}\end{array}$$

We now prove the full cycle of equivalences.

---

Proof: (I) $\Rightarrow$ (III) (Lipschitz gradient $\Rightarrow$ Descent Lemma).

Using the Fundamental Theorem of Calculus along the line segment $x+t(y-x)$:

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

Subtract the linear approximation at $x$:

$$\begin{array}{rl}f(y)-f(x)-⟨\mathrm{\nabla }f(x),y-x⟩& ={\int }_0^1⟨\mathrm{\nabla }f(x+t(y-x))-\mathrm{\nabla }f(x),y-x⟩dt\\ & \le {\int }_0^1\parallel \mathrm{\nabla }f(x+t(y-x))-\mathrm{\nabla }f(x)\parallel \cdot \parallel y-x\parallel dt\\ & \le {\int }_0^{1}L\cdot t\parallel y-x\parallel \cdot \parallel y-x\parallel dt\\ & =L\parallel y-x{\parallel }^2{\int }_0^{1}tdt=\frac{L}{2}\parallel y-x{\parallel }^2.\end{array}$$

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

---

Proof: (III) $\Rightarrow$ (II) (Descent Lemma $\Rightarrow$ $g$ convex).

Define $g(x)=\frac{L}{2}\parallel x{\parallel }^2-f(x)$. To show $g$ is convex, we verify the first-order condition. For any $x,y$:

$$\begin{array}{rl}g(y)-g(x)-⟨\mathrm{\nabla }g(x),y-x⟩& =[\frac{L}{2}\parallel y{\parallel }^2-f(y)]-[\frac{L}{2}\parallel x{\parallel }^2-f(x)]-⟨Lx-\mathrm{\nabla }f(x),y-x⟩\\ & =\frac{L}{2}\parallel y{\parallel }^2-\frac{L}{2}\parallel x{\parallel }^2-L⟨x,y-x⟩-[f(y)-f(x)-⟨\mathrm{\nabla }f(x),y-x⟩]\\ & =\frac{L}{2}\parallel y-x{\parallel }^2-[f(y)-f(x)-⟨\mathrm{\nabla }f(x),y-x⟩]\\ & \ge \frac{L}{2}\parallel y-x{\parallel }^2-\frac{L}{2}\parallel y-x{\parallel }^2=0,\end{array}$$

where the inequality uses condition (III). Hence $g(y)\ge g(x)+⟨\mathrm{\nabla }g(x),y-x⟩$, so $g$ is convex. $◻$

---

Proof: (II) $\Rightarrow$ (IV) (Convexity of $g$ $\Rightarrow$ Hessian bound).

If $g(x)=\frac{L}{2}\parallel x{\parallel }^2-f(x)$ is convex and twice differentiable, then ${\mathrm{\nabla }}^{2}g(x)⪰0$ for all $x$. Computing the Hessian:

$${\mathrm{\nabla }}^{2}g(x)=LI-{\mathrm{\nabla }}^{2}f(x).$$

Thus $LI-{\mathrm{\nabla }}^{2}f(x)⪰0$, i.e., ${\mathrm{\nabla }}^{2}f(x)⪯LI$. $◻$

---

Proof: (IV) $\Rightarrow$ (I) (Hessian bound $\Rightarrow$ Lipschitz gradient).

Assume ${\mathrm{\nabla }}^{2}f(x)⪯LI$ for all $x$. For any $x,y$, use the integral representation:

$$\parallel \mathrm{\nabla }f(y)-\mathrm{\nabla }f(x)\parallel =\Vert {\int }_0^1{\mathrm{\nabla }}^{2}f(x+t(y-x))(y-x)dt\Vert .$$

Since for any vector $v$, $\parallel {\mathrm{\nabla }}^{2}f(z)v\parallel \le \parallel {\mathrm{\nabla }}^{2}f(z){\parallel }_{\text{op}}\cdot \parallel v\parallel$ and ${\mathrm{\nabla }}^{2}f(z)⪯LI$ implies $\parallel {\mathrm{\nabla }}^{2}f(z){\parallel }_{\text{op}}\le L$, we have:

$$\parallel \mathrm{\nabla }f(y)-\mathrm{\nabla }f(x)\parallel \le {\int }_0^1\parallel {\mathrm{\nabla }}^{2}f(x+t(y-x)){\parallel }_{\text{op}}\cdot \parallel y-x\parallel dt\le L\parallel y-x\parallel .$$

Thus condition (I) holds. $◻$

This completes the chain of equivalences for L-smoothness.

---

3.12.2 Gradient Descent Convergence under Smoothness

Gradient descent updates:

$$\begin{array}{}\text{(3.9)}& x_{t+1}=x_t-\eta \mathrm{\nabla }f(x_t).\end{array}$$

Under L-smoothness alone, we can guarantee that the gradient norm converges to zero.

Lemma (Descent Lemma for gradient descent). If $f$ is L-smooth and we take $\eta =\frac{1}{L}$, then for each iteration:

$$\begin{array}{}\text{(3.10)}& f(x_{t+1})-f(x_t)\le -\frac{1}{2L}\parallel \mathrm{\nabla }f(x_t){\parallel }^2.\end{array}$$

Proof. Applying the Descent Lemma (condition III) with $y=x_{t+1}=x_t-\frac{1}{L}\mathrm{\nabla }f(x_t)$:

$$\begin{array}{rl}f(x_{t+1})& \le f(x_t)+⟨\mathrm{\nabla }f(x_t),x_{t+1}-x_t⟩+\frac{L}{2}\parallel x_{t+1}-x_t{\parallel }^2\\ & =f(x_t)-\frac{1}{L}\parallel \mathrm{\nabla }f(x_t){\parallel }^2+\frac{L}{2}\cdot \frac{1}{L^2}\parallel \mathrm{\nabla }f(x_t){\parallel }^2\\ & =f(x_t)-\frac{1}{2L}\parallel \mathrm{\nabla }f(x_t){\parallel }^2.\end{array}$$

Rearranging gives the claimed bound. $◻$

---

Theorem (Convergence to stationary point). Let $f$ be L-smooth and $f^{\ast }=\underset{x}{inf}f(x)>-\mathrm{\infty }$. After $T$ iterations of gradient descent with $\eta =\frac{1}{L}$:

$$\begin{array}{}\text{(3.11)}& \underset{0\le t\le T-1}{min}\parallel \mathrm{\nabla }f(x_t){\parallel }^2\le \frac{2L(f(x_0)-f^{\ast })}{T}.\end{array}$$

Consequently, $\underset{t<T}{min}\parallel \mathrm{\nabla }f(x_t)\parallel \to 0$ at a rate $O(1/\sqrt{T})$.

Proof. Summing the Descent Lemma over $t=0,1,\dots ,T-1$:

$$\begin{array}{rl}\sum _{t=0}^{T-1}(f(x_t)-f(x_{t+1}))& \ge \frac{1}{2L}\sum _{t=0}^{T-1}\parallel \mathrm{\nabla }f(x_t){\parallel }^2.\end{array}$$

The left-hand side telescopes:

$$f(x_0)-f(x_T)\ge \frac{1}{2L}\sum _{t=0}^{T-1}\parallel \mathrm{\nabla }f(x_t){\parallel }^2\ge \frac{T}{2L}\underset{0\le t\le T-1}{min}\parallel \mathrm{\nabla }f(x_t){\parallel }^2.$$

Since $f(x_T)\ge f^{\ast }$,

$$\frac{T}{2L}\underset{t<T}{min}\parallel \mathrm{\nabla }f(x_t){\parallel }^2\le f(x_0)-f^{\ast },$$

which rearranges to the stated bound. $◻$

This shows gradient descent converges to a stationary point (where $\mathrm{\nabla }f\approx 0$) at a rate $O(1/T)$.

---

3.12.3 Smooth + Convex Convergence

If $f$ is not only L-smooth but also convex, we obtain convergence to a global minimum (not just a stationary point).

Theorem (Convergence under smoothness + convexity). Let $f$ be L-smooth and convex, and let $x^{\ast }$ be a global minimizer of $f$. After $T$ iterations of gradient descent with $\eta =\frac{1}{L}$:

$$\begin{array}{}\text{(3.12)}& f(x_T)-f(x^{\ast })\le \frac{L}{2T}\parallel x_0-x^{\ast }{\parallel }^2.\end{array}$$

Proof. Write $\eta =\frac{1}{L}$. For each iteration:

$$\begin{array}{rl}\parallel x_{t+1}-x^{\ast }{\parallel }^2& =\parallel x_t-\eta \mathrm{\nabla }f(x_t)-x^{\ast }{\parallel }^2\\ & =\parallel x_t-x^{\ast }{\parallel }^2-2\eta ⟨\mathrm{\nabla }f(x_t),x_t-x^{\ast }⟩+{\eta }^2\parallel \mathrm{\nabla }f(x_t){\parallel }^2.\end{array}$$

By convexity (first-order condition), $f(x_t)-f(x^{\ast })\le ⟨\mathrm{\nabla }f(x_t),x_t-x^{\ast }⟩$. Hence:

$$-2\eta ⟨\mathrm{\nabla }f(x_t),x_t-x^{\ast }⟩\le -2\eta (f(x_t)-f(x^{\ast })).$$

Using the Descent Lemma (3.10), ${\eta }^2\parallel \mathrm{\nabla }f(x_t){\parallel }^2=\frac{1}{L^2}\parallel \mathrm{\nabla }f(x_t){\parallel }^2\le \frac{2}{L}(f(x_t)-f(x_{t+1}))$. Substituting:

$$\begin{array}{rl}\parallel x_{t+1}-x^{\ast }{\parallel }^2& \le \parallel x_t-x^{\ast }{\parallel }^2-\frac{2}{L}(f(x_t)-f(x^{\ast }))+\frac{2}{L}(f(x_t)-f(x_{t+1}))\\ & =\parallel x_t-x^{\ast }{\parallel }^2-\frac{2}{L}(f(x_{t+1})-f(x^{\ast })).\end{array}$$

Let ${\mathrm{\Delta }}_t=f(x_t)-f(x^{\ast })$. Then $\parallel x_{t+1}-x^{\ast }{\parallel }^2\le \parallel x_t-x^{\ast }{\parallel }^2-\frac{2}{L}{\mathrm{\Delta }}_{t+1}$, which implies:

$${\mathrm{\Delta }}_{t+1}\le \frac{L}{2}(\parallel x_t-x^{\ast }{\parallel }^2-\parallel x_{t+1}-x^{\ast }{\parallel }^2).$$

Summing this inequality from $t=0$ to $T-1$ telescopes:

$$\sum _{t=1}^T{\mathrm{\Delta }}_t\le \frac{L}{2}(\parallel x_0-x^{\ast }{\parallel }^2-\parallel x_T-x^{\ast }{\parallel }^2)\le \frac{L}{2}\parallel x_0-x^{\ast }{\parallel }^2.$$

Since ${\mathrm{\Delta }}_t$ is non-increasing (the Descent Lemma guarantees $f(x_{t+1})\le f(x_t)$), we have $T\cdot {\mathrm{\Delta }}_T\le \sum _{t=0}^{T-1}{\mathrm{\Delta }}_t\le \frac{L}{2}\parallel x_0-x^{\ast }{\parallel }^2$. Therefore:

$$f(x_T)-f(x^{\ast })\le \frac{L}{2T}\parallel x_0-x^{\ast }{\parallel }^2.◻$$

This is the $O(1/T)$ rate for smooth convex optimization.

---

3.12.4 m-Strongly Convex Functions

Definition (m-strongly convex function). A differentiable function $f:{\mathbb{R}}^n\to \mathbb{R}$ is called m-strongly convex for some $m>0$ if for all $x,y\in {\mathbb{R}}^n$,

$$\begin{array}{}\text{(3.13)}& f(y)\ge f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{m}{2}\parallel y-x{\parallel }^2.\end{array}$$

Strong convexity is a strengthened form of convexity that guarantees the function grows at least quadratically away from any point, ensuring a unique global minimum.

Remark. $m$ is often denoted $\mu$ in many texts. We keep $m$ for consistency with the lecture notation.

---

Chain of Equivalences. For a twice-differentiable function $f$, the following four statements are equivalent:

$$\begin{array}{rl}\text{(I)}& f(y)\ge f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{m}{2}\parallel y-x{\parallel }^2\text{(Strong FOC)}\\ \text{(II)}& h(x)=f(x)-\frac{m}{2}\parallel x{\parallel }^2\text{ is convex}\\ \text{(III)}& ⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge m\parallel x-y{\parallel }^2\text{(Strong Gradient Monotonicity)}\\ \text{(IV)}& {\mathrm{\nabla }}^{2}f(x)⪰mI\text{(Hessian bound)}\end{array}$$

---

Proof: (I) $\Rightarrow$ (II) (Strong FOC $\Rightarrow$ $h$ convex).

Define $h(x)=f(x)-\frac{m}{2}\parallel x{\parallel }^2$. For any $x,y$,

$$\begin{array}{rl}h(y)-h(x)-⟨\mathrm{\nabla }h(x),y-x⟩& =[f(y)-\frac{m}{2}\parallel y{\parallel }^2]-[f(x)-\frac{m}{2}\parallel x{\parallel }^2]-⟨\mathrm{\nabla }f(x)-mx,y-x⟩\\ & =f(y)-f(x)-⟨\mathrm{\nabla }f(x),y-x⟩-\frac{m}{2}(\parallel y{\parallel }^2-\parallel x{\parallel }^2-2⟨x,y-x⟩)\\ & =f(y)-f(x)-⟨\mathrm{\nabla }f(x),y-x⟩-\frac{m}{2}\parallel y-x{\parallel }^2\\ & \ge 0,\end{array}$$

where the last line uses condition (I). Hence $h(y)\ge h(x)+⟨\mathrm{\nabla }h(x),y-x⟩$, so $h$ is convex by the first-order condition. $◻$

---

Proof: (II) $\Rightarrow$ (IV) (Convexity of $h$ $\Rightarrow$ Hessian bound).

If $h(x)=f(x)-\frac{m}{2}\parallel x{\parallel }^2$ is convex and twice differentiable, then ${\mathrm{\nabla }}^{2}h(x)⪰0$ for all $x$. Computing the Hessian:

$${\mathrm{\nabla }}^{2}h(x)={\mathrm{\nabla }}^{2}f(x)-mI.$$

Thus ${\mathrm{\nabla }}^{2}f(x)-mI⪰0$, i.e., ${\mathrm{\nabla }}^{2}f(x)⪰mI$. $◻$

---

Proof: (IV) $\Rightarrow$ (III) (Hessian bound $\Rightarrow$ Strong Gradient Monotonicity).

Assume ${\mathrm{\nabla }}^{2}f(x)⪰mI$ for all $x$. For any $x,y$, use the integral representation:

$$\begin{array}{rl}⟨\mathrm{\nabla }f(y)-\mathrm{\nabla }f(x),y-x⟩& =⟨{\int }_0^1{\mathrm{\nabla }}^{2}f(x+t(y-x))(y-x)dt,y-x⟩\\ & ={\int }_0^1(y-x{)}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x+t(y-x))(y-x)dt\\ & \ge {\int }_0^{1}m\parallel y-x{\parallel }^{2}dt=m\parallel y-x{\parallel }^2.\end{array}$$

This establishes condition (III). $◻$

---

Proof: (III) $\Rightarrow$ (I) (Strong Gradient Monotonicity $\Rightarrow$ Strong FOC).

Assume $⟨\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y),x-y⟩\ge m\parallel x-y{\parallel }^2$. Using the Fundamental Theorem of Calculus:

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

Let $s=\parallel y-x\parallel$. Apply the strong monotonicity condition along the segment; for $z_t=x+t(y-x)$, evaluate with $x$ and $z_t$:

$$⟨\mathrm{\nabla }f(z_t)-\mathrm{\nabla }f(x),z_t-x⟩\ge m\parallel z_t-x{\parallel }^2=m{t}^2{s}^2.$$

Note that $z_t-x=t(y-x)$, so:

$$t\cdot ⟨\mathrm{\nabla }f(z_t)-\mathrm{\nabla }f(x),y-x⟩\ge m{t}^2{s}^2⟹⟨\mathrm{\nabla }f(z_t)-\mathrm{\nabla }f(x),y-x⟩\ge mt{s}^2.$$

Integrating over $t\in [0,1]$:

$${\int }_0^1⟨\mathrm{\nabla }f(x+t(y-x))-\mathrm{\nabla }f(x),y-x⟩dt\ge {\int }_0^{1}mt{s}^{2}dt=\frac{m}{2}{s}^2=\frac{m}{2}\parallel y-x{\parallel }^2.$$

Thus $f(y)\ge f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{m}{2}\parallel y-x{\parallel }^2$. $◻$

This completes the chain of equivalences for m-strong convexity.

---

3.12.5 Linear Convergence under Smooth + Strong Convexity

When a function is both L-smooth and m-strongly convex, gradient descent achieves linear (exponential) convergence to the unique global minimizer.

Theorem (Linear convergence). Let $f$ be L-smooth and m-strongly convex. Let $x^{\ast }$ be the unique global minimizer. Gradient descent with step size $\eta =\frac{1}{L}$ satisfies:

$$\begin{array}{}\text{(3.14)}& f(x_T)-f(x^{\ast })\le {(1-\frac{m}{L})}^T(f(x_0)-f(x^{\ast })).\end{array}$$

Proof. From the Descent Lemma with $\eta =\frac{1}{L}$:

$$f(x_{t+1})\le f(x_t)-\frac{1}{2L}\parallel \mathrm{\nabla }f(x_t){\parallel }^2.$$

By m-strong convexity, we have a lower bound relating the gradient norm to the optimality gap. For any $x$,

$$f(x^{\ast })\ge f(x)+⟨\mathrm{\nabla }f(x),x^{\ast }-x⟩+\frac{m}{2}\parallel x^{\ast }-x{\parallel }^2.$$

Minimizing the right-hand side over $y$ (a quadratic in $y$) gives:

$$f(x^{\ast })\ge f(x)-\frac{1}{2m}\parallel \mathrm{\nabla }f(x){\parallel }^2,$$

since $\underset{y}{min}\{f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{m}{2}\parallel y-x{\parallel }^2\}=f(x)-\frac{1}{2m}\parallel \mathrm{\nabla }f(x){\parallel }^2$.

Rearranging yields the Polyak–Łojasiewicz (PL) inequality:

$$\begin{array}{}\text{(3.15)}& \parallel \mathrm{\nabla }f(x){\parallel }^2\ge 2m(f(x)-f(x^{\ast })).\end{array}$$

Plug this into the Descent Lemma:

$$\begin{array}{rl}f(x_{t+1})-f(x^{\ast })& \le f(x_t)-f(x^{\ast })-\frac{1}{2L}\cdot 2m(f(x_t)-f(x^{\ast }))\\ & =(1-\frac{m}{L})(f(x_t)-f(x^{\ast })).\end{array}$$

Unrolling this inequality over $T$ iterations gives:

$$f(x_T)-f(x^{\ast })\le {(1-\frac{m}{L})}^T(f(x_0)-f(x^{\ast })).◻$$

---

Definition (Condition number). The ratio

$$\kappa =\frac{L}{m}\ge 1$$

is called the condition number of $f$. It measures how "elongated" the sublevel sets of $f$ are.

Since $0<m\le L$, we have $\kappa \ge 1$. The convergence rate can be rewritten as:

$$f(x_T)-f(x^{\ast })\le {(1-\frac{1}{\kappa })}^T(f(x_0)-f(x^{\ast })).$$

Using the inequality $1-x\le e^{-x}$, we obtain the more intuitive bound:

$$f(x_T)-f(x^{\ast })\le \exp (-\frac{T}{\kappa })(f(x_0)-f(x^{\ast })).$$

To achieve $f(x_T)-f(x^{\ast })\le \epsilon$, it suffices to take

$$T\ge \kappa \log \frac{f(x_0)-f(x^{\ast })}{\epsilon },$$

which is linear in the condition number $\kappa$. When the function is well-conditioned (small $\kappa$), gradient descent converges rapidly. For ill-conditioned problems (large $\kappa$), convergence can be slow.

---

Summary. The interplay between smoothness and strong convexity is fundamental to first-order optimization:

Property	Guarantee	Rate
L-smooth only	$\underset{t<T}{min}|\mathrm{\nabla }f(x_t){|}^2\le O(1/T)$	Sublinear to stationary point
L-smooth + convex	$f(x_T)-f(x^{\ast })\le O(1/T)$	Sublinear to global minimum
L-smooth + m-strongly convex	$f(x_T)-f(x^{\ast })\le (1-m/L{)}^T{\mathrm{\Delta }}_0$	Linear (exponential)

Strong convexity is what transforms the sublinear rate of gradient descent into a linear (geometric) rate, with the condition number $\kappa =L/m$ governing the constant.