A first look at convex analysis

Refer to caption — Figure 1: Definition of concavity by Archimede

Despite the fact that many problems encountered in statistics and machine learning are not convex, convexity is an important to study in order to understand what is the generic behaviour of an optimization procedure.

1 Convex set

A set $C\subseteq\mathcal{X}$ is convex if every segment of $C$ is contained in $C$ . It can formalized as the following definition and illustrated in Figure 2.

Figure 2: Left: convex set. Right: not a convex set.

Definition 1.

A set $C\subseteq\mathcal{X}$ is convex if

\forall(x,y)\in C^{2},\forall\lambda\in[0,1],\quad\lambda x+(1-\lambda)y\in C.

In most of these lecture notes, the set $\mathcal{X}$ will the Euclidean space $\mathbb{R}^{p}$ , but remark that this notion only requires that $\mathcal{X}$ is a vector space over the real numbers $\mathbb{R}$ , possibly of infinite dimension.

Example 1.

•

The convex sets of $\mathbb{R}$ are exactly the intervals of $\mathbb{R}$ .
•

Any affine hyperplane $H=\{x\in\mathcal{X}\mid\varphi(x)=\alpha\}$ where $\mathcal{X}$ is a real vector space, $\varphi$ a linear functional and $\alpha\in\mathbb{R}$ is convex.
•

Any half-space $H_{-}=\{x\in\mathcal{X}|\varphi(x)\leq\alpha\}$ is also convex.
•

The unit simplex of $\mathbb{R}^{d}$ defined as

\Delta^{d-1}=\{x\in\mathbb{R}^{d}\mid x_{i}\geq 0\text{ and }\sum_{i}x_{i}=1\}

is convex.

•

The nonnegative orthant $\mathbb{R}_{\geq 0}^{d}=\{x\in\mathbb{R}^{d}|x_{i}\geq 0\}$ is convex.

The following proposition reviews some important algebraic properties of convex sets.

Proposition 1.

•

Arbitrary intersection. Let $(C_{i})_{i\in I}$ convex sets where $I$ is a set. Then $\cap_{i\in I}C_{i}$ is convex.
•

Cartesian product. Let $C_{1},\dots,C_{n}$ be sets of $\mathbb{R}^{n_{1}},\dots,\mathbb{R}^{n_{n}}$ . Then $C_{1}\times\dots\times C_{n}$ is convex if, and only if, every $C_{i}$ is convex.
•

Sum. Let $C_{1}$ , $C_{2}$ two convex sets. Then the (Minkowski) sum $C_{1}+C_{2}$ is convex.
•

Affine map. Let $A:\mathbb{R}^{n}\to\mathbb{R}^{m}$ be an affine map and $C\subseteq\mathbb{R}^{n}$ a convex set. Then the image $A(C)$ is convex.

2 Convex functions

The intuitive definition of a convex function is a function such that “the line joining $f(x)$ and $f(y)$ lies above the graph of $f$ between $x$ and $y$ ”. Formally, this definition makes sense using the definition of the epigraph of $f$ .

Definition 2.

Let $f:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ and $f\neq+\infty$ . The epigraph of $f$ is the subset of $\mathbb{R}^{n}\times\mathbb{R}$ defined by

\mathrm{epi}f:=\{(x,t)\in\mathbb{R}^{n}\times\mathbb{R}\mid t\geq f(x)\}.

Figure 3: (Left) Epigraph of a concave function. (Right) Epigraph of a convex function.

Equipped with this notion, we can define convex functions using the definition of convex sets applied to the epigraph.

Definition 3.

A function $f:\mathbb{R}^{p}\to\overline{\mathbb{R}}$ such that $f\neq+\infty$ is convex function iff its epigraph $\text{epi}f$ is convex.

It is possible to make explicit this definition as follow:

\forall x,y\in\mathrm{dom}f,\,\forall\lambda\in[0,1],\qquad f(\lambda x+(1-% \lambda)y)\leq\lambda f(x)+(1-\lambda)f(y).

(1)

Following the convention introduced in (Hiriart-Urruty, Jean-Baptiste and Lemarechal, Claude, 1996), we will denote the set of all convex functions of $\mathbb{R}^{p}$ as $\operatorname{Conv}\mathbb{R}^{p}$ , and the set of closed – that is, with closed epigraph – convex functions of $\mathbb{R}^{p}$ as $\overline{\operatorname{Conv}}\mathbb{R}^{p}$ .

2.1 Local and global minima of a convex function

For a (un)constrained minimization problem on a convex set $C\subseteq\mathrm{dom}f$ with a function $f:C\to\mathbb{R}$ ,

\min_{x\in C}f(x),

(2)

we say that $x^{\star}$ is

•

a local solution of (2), if there exists a neighborhood $\mathcal{O}$ of $x^{\star}$ such that for all $x\in C\cap\mathcal{O}$ , $f(x)\geq f(x^{\star})$ ;
•

a (global) solution if for all $x\in C$ , $f(x)\geq f(x^{\star})$ .

A fundamental result is that, when $f$ is convex, every local solution of (2) is global solution, and the set of (global) solutions is a convex set.

Theorem 1.

Assume that $f$ is a convex function and $C$ is a convex closed set. Then,

•

Any local solution of (2) is a global solution;
•

The set of global solutions of (2) is convex.

Proof.

Part 1. By contradiction. Consider a local solution $x^{\star}$ and assume that $x^{\star}$ is not a global solution. In particular, there exists $z\in C$ such that $f(z)<f(x^{\star})$ . By convexity,

f((1-t)x^{\star}+tz)\leq(1-t)f(x^{\star})+tf(z)<f(x^{\star})\quad\forall t\in[% 0,1]

Given any open neighborhood $\mathcal{O}$ of $x^{\star}$ , there exists $t>0$ such that $(1-t)f(x^{\star})+tf(z)<f(x^{\star})$ (contradiction).

Part 2. Take two global solutions, and study the segment joining it: let $x^{\star}$ and $z$ two solutions. We have $f(x^{\star})=f(z)$ , and in turn,

f(x^{\star})\leq f((1-t)x^{\star}+tz)\leq(1-t)f(x^{\star})+tf(z)=f(x^{\star}),

where the first inequality comes from the equality of the function at $x^{\star}$ and $z$ , and the second by convexity. ∎

2.2 Differentiable properties of a convex function

A differentiable function is convex if, and only if, it is above all its tangents, see Figure 4.

Figure 4: A differentiable convex function and its tangent. The curve is always above its tangent in red.

Proposition 2.

Let $f$ be a differentiable function on an open set $\Omega\subseteq\mathbb{R}^{p}$ , and $C\subseteq\Omega$ a convex subset of $\Omega$ . Then $f$ is convex on $C$ if, and only if,

\forall x,\bar{x}\in C,\quad f(x)\geq f(\bar{x})+\langle{\nabla f(\bar{x})},{x% -\bar{x}}\rangle.

(3)

Proof.

Assume $f$ is convex on $C$ . Let $x,\bar{x}\in C$ and $\lambda\in(0,1)$ . By definition of convexity, we have

f(\lambda x+(1-\lambda)\bar{x})-f(\bar{x})\leq\lambda(f(x)-f(\bar{x})).

Dividing by $\lambda$ , and letting $\lambda$ goes to 0, we obtain (3).

Reciprocally, let $x,y\in C$ , $\lambda\in(0,1)$ and define $z=\alpha x+(1-\alpha)y\in C$ . Applying (3) twice, we have

	$\displaystyle f(x)$	$\displaystyle\geq f(z)+\langle{\nabla f(z)},{x-z}\rangle$
	$\displaystyle f(y)$	$\displaystyle\geq f(z)+\langle{\nabla f(z)},{y-z}\rangle.$

Using a convex combination of these two lines, we get

\alpha f(x)+(1-\alpha)f(y)\geq f(z)+\langle{\nabla f(x)},{\alpha x+(1-\alpha)y% -z}\rangle,

which is exactly (1). ∎

A similar criterion can be derived for strictly convex function. Remark that Theorem 1 is a direct consequence of Proposition prop-convex-diff for the class of differentiable convex functions: a local minima $x^{\star}$ satisfies $\nabla f(x^{\star})=0$ and thus (3) gives $f(x)\geq f(x^{\star})$ for all $x\in C$ .

3 Strongly convex functions

A strongly convex function satisfies a stronger statement of the Jensen’s inequality.

Definition 4.

A function $f:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ is strongly convex of modulus $\mu>0$ if $\mathrm{dom}f$ is convex and

f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)-\frac{1}{2}\mu% \lambda(1-\lambda)\|x-y\|^{2},

for all $x,y\in\mathrm{dom}f$ and $\lambda\in[0,1]$ .

Another way to define strongly convex function is to say that $f$ is $\mu$ -strongly convex if the function

x\mapsto f(x)-\frac{\mu}{2}\|x\|^{2}

is a convex function.

A strongly convex function defined on the whole space $\mathbb{R}^{d}$ has a unique minimizer.

3.1 Differentiability, strong convexity and quadratic lower bound

A function $f$ is strongly convex if, and only if, it is strictly above its tangent, and you can “fit” a quadratic form between the tangent and the function itself. This is a key property to defined lower bounds on $f$ .

Figure 5: Strong convexity and differentiability. There is space for a quadratic form between the curve

y=f(x)

and the tangent.

Proposition 3.

Let $f$ be a differentiable and $\mu$ -strongly convex function. Then,

\forall x,\bar{x}\in\mathrm{dom}f,\quad f(x)\geq f(\bar{x})+\langle{\nabla f(% \bar{x})},{x-\bar{x}}\rangle+\frac{\mu}{2}\|x-\bar{x}\|^{2}.

Note that if $f$ is $C^{2}$ , $f$ is $\mu$ -strongly convex if, and only if, its Hessian $\nabla^{2}f\geq\mu\mathrm{Id}$ , i.e., is definite positive.

An easy consequence is that it is possible to establish a lower bound on the values based on a lower bound on the distance between points:

f(x)\geq f(x^{\star})+\frac{\mu}{2}\|x-x^{\star}\|^{2},

(4)

where $x^{\star}$ is the minimizer of $f$ .

4 Lipschitz continuity of the gradient

Definition 5.

A differentiable function $f:\mathbb{R}^{n}\to\mathbb{R}$ is said to be $L$ -smooth if $\nabla f$ is $L$ -Lipschitz, i.e.,

\forall x,y\in\mathrm{dom}f,\quad\|\nabla f(x)-\nabla f(y)\|_{*}\leq L\|x-y\|.

Here $\|\cdot\|_{*}$ is the dual norm of $\|\cdot\|$ .

4.1 Quadratic upper bound

$L$ -smoothness is important in optimization because it ensures a quadratic upper bound of the function.

Proposition 4.

Let $f$ a $L$ -smooth function. Then, for all $x,y\in\mathrm{dom}f$ ,

\langle\nabla f(x)-\nabla f(y),x-y\rangle\leq L\|x-y\|^{2}.

(5)

Moreover, if $\mathrm{dom}f$ is convex, then (5) is equivalent to

f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\|x-y\|^{2},\quad% \forall x,y\in\mathrm{dom}f.

(6)

Proof.

The fact that $L$ -smoothness implies (5) is a direct application of the (generalized) Cauchy-Schwarz inequality. For the equivalence of (5) and (6), let’s prove the two direction.

Given $x,y\in\mathrm{dom}f$ , define the real function $g(t)=f(x+t(y-x))$ . Assuming (5) holds, then

g^{\prime}(t)-g^{\prime}(0)=\langle\nabla f(x+t(y-x))-\nabla f(x),y-x\rangle% \leq tL\|x-y\|^{2}.

Now,

	$\displaystyle f(y)=g(1)=g(0)+\int_{0}^{1}g^{\prime}(t)$	$\displaystyle\leq g(0)+g^{\prime}(0)+\frac{L}{2}\\|x-y\\|^{2}$
		$\displaystyle=f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\\|x-y\\|^{2}.$

Reciprocally, if (5) holds, it is sufficient to apply it twice (to $x, y$ and $y, x$ ) and combine the two equations. ∎

This result has a strong implication on the minima of $f$ .

Proposition 5.

Let $f$ be a $L$ -smooth function with full domain, and assume $x^{\star}$ is a minimizer of $f$ . Then,

\frac{1}{2L}\|\nabla f(z)\|_{*}^{2}\leq f(z)-f(x^{\star})\leq\frac{L}{2}\|z-x^% {\star}\|^{2}\quad\forall z\in\mathbb{R}^{n}.

Proof.

The two side are proved separately.

rhs: Apply (5) applied to $(x^{\star},z)$ .

lhs: Minimize the quadratic upper bound for $x=z$ :

	$\displaystyle f(x^{\star})=\min_{y\in\mathbb{R}^{n}}f(y)$	$\displaystyle\leq\inf_{y}\left(f(z)+\langle\nabla f(z),y-z\rangle+\frac{L}{2}% \\|y-z\\|^{2}\right)$
		$\displaystyle=\inf_{\\|v\\|=1}\inf_{t}\left(f(z)+t\langle\nabla f(z),v\rangle+% \frac{Lt^{2}}{2}\right),$

where the last inequality is obtained by the change of variable $v=\frac{w}{\|w\|}$ , $t=\|w\|$ and $w=y-z$ . Factorizing the trinom in $t$ leads to:

f(z)+t\langle\nabla f(z),v\rangle+\frac{Lt^{2}}{2}=\frac{L}{2}\left(t+\frac{1}% {L}\langle\nabla f(z),v\rangle\right)^{2}-\frac{1}{2L}\langle\nabla f(z),v% \rangle^{2}+f(z).

Hence,

\min_{y\in\mathbb{R}^{n}}f(y)\leq\inf_{\|v\|=1}\left(f(z)-\frac{1}{2L}\langle% \nabla f(z),v\rangle^{2}\right).

Minimizing the infimum boils down to maximizing $\langle\nabla f(z),v\rangle^{2}$ , that is obtained with $v=\nabla f(z)$ , hence the result. ∎

4.2 Co-coercivity of the gradient of a $L$ -smooth function

Convex $L$ -smooth functions are co-coercive. This result is sometimes coined Baillon–Haddad theorem (Baillon, Jean-Bernard and Haddad, Georges, 1977), but one shall note that the original contributionis much more general than its application to the gradient.

Proposition 6.

Let $f$ be a full-domain convex $L$ -smooth function. Then, $\nabla f$ is $1/L$ -co-coercive, i.e.,

\forall x,y\in\mathbb{R}^{n},\quad\langle\nabla f(x)-\nabla f(y),x-y\rangle% \geq\frac{1}{L}\|\nabla f(x)-\nabla f(y)\|_{*}^{2}.

Proof.

Let $f_{x}(z)=f(z)-\langle\nabla f(x),z\rangle$ and $f_{y}(z)=f(z)-\langle\nabla f(y),z\rangle$ . The two are convex.

Since $f$ is $L$ -smooth, $f_{x}$ and $f_{y}$ are also $L$ -smooth.

Canceling the gradient of $f_{x}$ shows that $z=x$ minimizes $f_{x}$ . Hence, using the quadratic upper bound, we have

	$\displaystyle f(y)-f(x)-\langle\nabla f(x),x-y\rangle$	$\displaystyle=f_{x}(y)-f_{x}(x)$
		$\displaystyle\geq\frac{1}{2L}\\|\nabla f_{x}(y)\\|_{*}^{2}$
		$\displaystyle=\frac{1}{2L}\\|\nabla f(y)-\nabla f(x)\\|_{*}^{2}.$

Doing exactly the same thing for $f_{y}$ leads a similar bound, and combining the two gives the result. ∎

It turns out that smoothness, co-coercivity and upper quadratic boundness are equivalent properties for full-domain convex function.

Proposition 7.

Let $f$ be a differentiable convex function with $\mathrm{dom}f=\mathbb{R}^{n}$ . Then the three following properties are equivalent:

1.

$f$ is $L$ -smooth.
2.

The quadratic upper bound (6) holds.
3.

$\nabla f$ is $1/L$ -co-coercive.

Proof.

The only one to prove is 2. $\implies$ 3. (by Cauchy-Schwarz). ∎

For the special case of the $\ell^{2}$ norm, we have:

Proposition 8.

Let $f$ be a differentiable convex function with $\mathrm{dom}f=\mathbb{R}^{n}$ , and $L$ -smooth with respect to the Euclidean norm. Then,

1.

$L\mathrm{Id}-\nabla f$ is monotone, i.e.

\forall x,y\in\mathbb{R}^{n},\quad\langle\nabla f(x)-\nabla f(y),x-y\rangle% \leq L\|x-y\|_{2}^{2}.

1.

$\frac{L}{2}\|x\|_{2}^{2}-f(x)$ is convex.
2.

If $f$ is twice differentiable, then,

\lambda_{\mathrm{max}}(\nabla^{2}f(x))\leq L,\quad\forall x\in\mathbb{R}^{n}.

When $f$ is both $L$ -smooth and $\mu$ -strongly convex, we have the following “strenghened” co-coercivity.

Proposition 9.

Let $f$ be a $L$ -smooth and $\mu$ -strongly convex function. For any $x,y\in\mathbb{R}^{n}$ , we have

\langle{\nabla f(x)-\nabla f(y)},{x-y}\rangle\geq\frac{\mu L}{\mu+L}\|x-y\|^{2% }+\frac{1}{\mu+L}\|\nabla f(x)-\nabla f(y)\|^{2}.

Proof.

Consider the convex function $\phi(x)=f(x)-\frac{\mu}{2}\|{x}\|^{2}$ . Its gradient reads $\nabla\phi(x)=\nabla f(x)-\mu x$ . Using the $L$ -smoothness of $f$ , we have that

	$\displaystyle\langle{\nabla\phi(x)-\nabla\phi(y)},{x-y}\rangle$	$\displaystyle=\langle{\nabla f(x)-\nabla f(y)},{x-y}\rangle-\mu\langle{x-y},{x% -y}\rangle$
		$\displaystyle\leq(L-\mu)\\|{x-y}\\|^{2}.$

Hence, $\phi$ is $(L-\mu)$ -smooth.

If $L=\mu$ , then nothing is left to prove since $f$ is $\mu$ -strongly convex. Otherwise, the $(L-\mu)$ -co-coercivity of $\phi$ (Proposition 6) gives us

\langle{\nabla\phi(x)-\nabla\phi(y)},{x-y}\rangle\geq\frac{1}{L-\mu}\|{\nabla% \phi(x)-\nabla\phi(y)}\|^{2}.

Explicing the expression of $\nabla\phi(x)$ allows us to conclude. ∎

Baillon, Jean-Bernard and Haddad, Georges (1977). Quelques propriétés des opérateurs angle-bornés etn-cycliquement monotones.

Hiriart-Urruty, Jean-Baptiste and Lemarechal, Claude (1996). Convex Analysis and Minimization Algorithms I: Fundamentals, Springer.

A first look at convex analysis

1 Convex set

Definition 1.

Example 1.

Proposition 1.

2 Convex functions

Definition 2.

Definition 3.

2.1 Local and global minima of a convex function

Theorem 1.

Proof.

2.2 Differentiable properties of a convex function

Proposition 2.

Proof.

3 Strongly convex functions

Definition 4.

3.1 Differentiability, strong convexity and quadratic lower bound

Proposition 3.

4 Lipschitz continuity of the gradient

Definition 5.

4.1 Quadratic upper bound

Proposition 4.

Proof.

Proposition 5.

Proof.

4.2 Co-coercivity of the gradient of a L-smooth function

Proposition 6.

Proof.

Proposition 7.

Proof.

Proposition 8.

Proposition 9.

Proof.

4.2 Co-coercivity of the gradient of a $L$ -smooth function