Convexity

Convexity

A function $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex $⟺\forall z_1\ne z_2$ and $\forall \lambda \in (0,1)$ the following condition holds:

$$f(\lambda \cdot z_1+(1-\lambda )z_2)\le \lambda f(z_1)+(1-\lambda )\cdot f(z_2)$$

Strict Convexity

And the function $f:{\mathbb{R}}^n\to \mathbb{R}$ then becomes strictly convex $⟺\forall z_1\ne z_2$ and $\forall \lambda \in (0,1)$ the following condition holds:

$$f(\lambda \cdot z_1+(1-\lambda )z_2)<\lambda f(z_1)+(1-\lambda )\cdot f(z_2)$$

The key difference between a function being convex or strictly convex being in the $\le$ and $<$ signs.

Proving Convex Functions

Convex function inequality

$f(\lambda x_1+(1-\lambda )x_2)\le \lambda f(x_1)+(1-\lambda )f(x_2)$

1. Pick two points above the function $f(x)$ such as $(x_1,x_2)=(0,1)$
2. Substitute points into the above inequality. If it holds then the function is convex. If not then the function is not convex.

Convex, non-differentiable functions

It is possible to have functions that are convex, but not differentiable. One example is the modulus function: $f(x)=|x|$ where $\nexists f(x{)}^{\prime }$.

Non-convex Functions

Convex Matrices

Convex matrices must be positive semi-definite, hence must be symmetric ie $A=A^T$. The conditions for a PSD matrix are as follows:

Positive Semi-Definite (PSD)

There are two ways which we can see if a matrix is positive semi-definite.

• 1. Eigen values $\lambda \ge 0$

  In this case, we need to ensure that all eigenvalues of the matrix are greater than zero. This implies they are all definitely positive, ie $\lambda \ge 0\forall \lambda$.

• 2. Leading principle minors ${\Delta }_{\mathrm{1...}n}\ge 0$

  In this case, we need to ensure that all eigenvalues of the matrix are greater than zero. This implies they are all definitely positive, ie $\Delta \ge 0\forall \Delta$.

There is a shortcut to checking whether a matrix is PSD. We check whether the quadratic product is greater than or equal to zero.

${\vec{x}}^T\cdot A\cdot \vec{x}\ge 0$

For a given symmetric matrix $A$

$A=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$

We check for the quadratic product on $A$ giving

(0)^2+x_2^2 \ge 0 $$ Hence, we say $A$ is PSD given that $\vec x$ contains one positive and one zero value.