Convexity

Convex functions are some of the most studied functions in mathematics and engineering. In this article we will explore a wide range of convex functions that are studied in mathematical optimization. Mathematically a function $f : \mathcal{K} \rightarrow \mathbb{R}$ is called convex if for all
$\alpha \in (0,1) \text{ and } x_1, x_2 \in \mathcal{K}$

f(\alpha x_1 + (1-\alpha)x_2) \le \alpha f(x_1) + (1-\alpha) f(x_1)

In common terms, a line segment joining any two points in the domain of $f$ always lie on or above the curve generated by $f$ . In other words, $f$ is atleast linear everwhere.

1. Properties of convex functions

A convex function may not have a local minima $e.g., e^x$ . Even if a local minima exist, it may not be unique.
If a convex function has more than one local minima say $x_1$ and $x_2$ , all points in the line segment joining $x_1$ and $x_2$ are local minima.
If a convex function has a unique local minima, it is a global minima.
The average of the functional values of some randomly selected points sits on top of the function at the average of these points. This is called Jensen’s inequality

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

A differentiable function is convex iff the tangent at any point $x \in \mathcal{K}$ lies below the function everywhere else.

f(y) \ge f(x) + \nabla f(x)^T (y-x)

Non-negative weighted sum of convex functions is always convex.
Function composition of a convex function with a affine mapping results in a convex function.
For convex functions $\{f_i\}, i \in [n]$ , the point wise minima $f(x) = \min_{i}\{f_i(x)\}$ is convex.

Although a convex function has ‘nice’ properties, they are not sufficient to guarantee some result. For example, a iterative algorithm is guaranteed to reach a local minima but it may not be the most desired. In such cases, we need a stronger convexity called stong convex functions.

2. Strong Convex Functions

A strong convex function has a strictly positive lower bound on its curvature, i.e., it grows atleast as fast as a quadratic function everywhere. A $\alpha$ -strongly convex function is defined as

f(y) \ge f(x) + \nabla f(x)^T(y-x) + \frac{\alpha}{2} ||y-x||^2

This means for a $\alpha$ -convex function $f, f-\frac{\alpha}{2}x^2$ is still a convex function. Some convex functions like linear functions, $e^x, |x|, x^4$ and higher order even polynomial function are not strongly convex. Exponential function $e^x$ becomes flat as $x \rightarrow -\infty, x^4$ is flat around $0$ therefore, they are not strongly convex. Surprisingly, there in an infinite numbers of family of strongly convex functions.

2.1. Properties of strongly convex functions

A strongly convex function has a unique global minima.
Unlike a convex function that only stays above the tangent line, a strongly convex function also stays above a parabola.
When $||x|| \rightarrow \infty$ , a strongly convex function $f \rightarrow \infty$ .