Federico Mengozzi

Convex Analysis

Convex set

Given a finite set of points $z_1, z_2, \dots, z_n \in \mathbb{R}^n$, a point $z \in \mathbb{R}^n$ is called convex combination if \[z = \sum\limits_{j=1}^n t_ix_y\]

with $t_j \geq 0, \forall j$ and $\sum_{j=1}^n t_j = 1$. If $t_j > 0, \forall j$ the point is called strict convex combination

By induction it’s possible to show that a convex set $S$ of size $n$ contains all combination of $n$ points.

With $n = 2$ the set contains all the point on the segment $tx + (1-t)y, \forall 0 < t < 1$

When $n = 3$, it’s sufficient to prove that $z = t_1z_1 + t_2z_2 + t_3z_3 \in S$, but since $t_1 + t_2 = 1 - t_3$ and $z = (1-t_3)(\dfrac{t_1}{t_1 + t_2}z_1 + \dfrac{t_2}{t_1 + t_2}z_2) + t_3z_3$

It follows that $z’ = \dfrac{t_1}{t_1 + t_2}z_1 + \dfrac{t_2}{t_1 + t_2}z_2 \in S$ since it contains all combination of pairs. And also $z’ + t_3z_3 \in S$

Convex hull

The set of all convex combinations of finite sets of points convex $H$ of a set $S \in \mathbb{R}^m$ is defines as follow \[H = \Big\{ z = \sum\limits_{j=1}^n t_jz_j : n \geq 1, z_y \in S \land t_j > 0 \forall j \land \sum\limits_{j=1}^n t_j = 1 \Big\}\]

Caratheodory’s theorem

The convex hull $conv(S)$ of a set $S \in \mathbb{R}^m$ is define as \[H = \Big\{ z = \sum\limits_{j=1}^{m+1} t_jz_j : n \geq 1, z_y \in S \land t_j > 0 \forall j \land \sum\limits_j t_j = 1 \Big\}\]

Go to top