2  Convexity

2.1 Convex sets

Definition 2.1 (Convex set) A set C \subseteq \mathbb R^d is convex if for all x, y \in C and \lambda \in [0,1] (1-\lambda) x + \lambda y \in C

Definition 2.2 (Span) \text{span}(S) := \left\{ \sum_{i=1}^N a_i x_i: x_i \in S \right\}

Definition 2.3 (Affine hull) \text{aff}(S) := \left\{ \sum_{i=1}^N a_i x_i: x_i \in S, \sum_{i=1}^N a_i = 1 \right\}

Definition 2.4 (Convex hull) \text{conv}(S) := \left\{ \sum_{i=1}^N a_i x_i: x_i \in S, a_i \geq 0, \sum_{i=1}^N a_i = 1 \right\}

Note that \text{conv}(S) \subseteq \text{aff}(S) \subseteq \text{span}(S)

2.1.1 Operations preserving convexity of sets

If K, K_1, K_2, (K_i)_{i \in I} are convex then so are the sets defined by:

• Intersection: \cap_{i \in I} K_i
• Scalar multiplication: cK = \{cx: x \in K\}
• Addition: K_1 + K_2 = \{x_1 + x_2: x_1 \in K_1, x_2 \in K_2\}
• Affine transform: AK + b =\{Ax + b: x \in K\}

2.1.2 Halfspace representation

Closed convex K \subseteq \mathbb R^n is the intersection of all containing halfspaces K \equiv \cap_{H \supseteq K} H

Proof

For every H, K \subseteq H thus it is subset of the intersection as well. For the converse- consider a point z not in K. By separating hyperplane theorem we get w \in \mathbb R^n such that \langle w, z\rangle > b > \sup_{x \in K} \langle w, x \rangle

Then we can take the halfspace defined by \langle w, x\rangle \leq b which contains K but not z, which means z does not lie in the intersection

2.2 Convex functions

Definition 2.5 (Zeroth order definition) A function f: S (\subseteq \mathbb R^d) \to \mathbb R is convex if for all x, y \in S i.e. \text{dom}(f) and \lambda \in [0,1] f((1-\lambda) x + \lambda y) \leq (1-\lambda) f(x) + \lambda f(y)

We can use the convention that f(x \notin S) := +\infty which upholds the above inequality for all x, y.

For convex f, x is a global minimum iff it is a local minimum.

2.2.1 First order definition

If f is differentiable, then f is convex iff:

f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle

2.2.1.1 Affine function

l(x) = \langle a, x\rangle + b

2.2.1.2 Quadratic function

l(x) = \langle x, Ax\rangle + \langle b, x \rangle + c

where A \in \mathbb R^{n \times n} is symmetric wlog

2.2.1.3 Indicator of convex set

\delta_K := \begin{cases} 0& x \in K\\ \infty &o.w\end{cases}

2.2.1.4 Support function of convex set

h_K(y) := \sup_{x \in K} \langle y, x\rangle

2.2.2 Operations preserving convexity

• Non-negative scalar multiplication: f \to c f
• Addition: f_1 + f_2
• Pointwise supremum: \sup_{i \in I} f
• Restriction to a line or subspace: l := t \mapsto tx + (1-t)y then f\circ l is convex
• Affine transform: x \mapsto f(Ax + b)
• Perspective: (x, t)\mapsto t f({x}/{t}) for t >0

2.2.3 Epigraph

For \mathbb R^n \to \mathbb R, define the epigraph as the subset of \mathbb R^{n+1} such that:

\text{epi} (f) := \{(x, t) | f(x) \leq t\}

f is a closed (lower semicontinuous) convex function iff its epigraph is a closed and convex set.

Lemma 2.1 For convex f and any t\in \mathbb R, the sub level set

L_t(f) := \{ x \in \mathbb R^n | f(x) \leq t\}

is a convex set.

2.2.4 Affine minorant representation

Closed convex proper (never -\infty and not always \infty) function f: \mathbb R^n \to \mathbb R is the supremum of all affine minorants f(x) = \sup_{f \geq h} h(x)

Since all f(x) \geq h(x), f(x) \geq \sup h(x).

2.3 Separating hyperplanes

For every convex set K and point p \notin K, there is a separating hyperplane w \in \mathbb R^n satisfying:

\max_{x \in K} \langle w,x \rangle < b < \langle w, p\rangle

Proof

Let x^* = \arg \inf_{x\in K} \|x-p\|^2_2 be the closest point in K to p. Then the claim is that x^* - p is a separating hyperplane.

We need to show this is well defined. So take any x_0 \in K and consider:

L:= K \cap \{ y \in K| \|y-p\|^2_2 \leq \|x_0-p\|_2^2 \}

L is convex because K and the second set (sublevel set of 2 norm- a convex function) both are. L is closed and bounded so compact.

Now notice that if it exists, \|x^* -p\| \leq \|x_0-p\| i.e. any minimiser of \|x- p\| must live inside the ball around x_0. And since L is compact and \|x-p\|^2_2 continuous, by the extreme value theorem it attains this value within L so x^* exists.

Next we can show x^* = \arg \inf \iff \forall x \in K , \langle x-x^*, x^* -p \rangle \geq 0:

\begin{align*} \|x-p\|^2 - \|x^* - p\|^2 &= \|x- x^* + x^*-p\|^2 - \|x^* - p\|^2\\ &= 2 \langle x-x^*, x^* -p \rangle + \|x-x^*\|^2 \\ &\geq 0 \end{align*}

If the cross product is positive for all x, then x^* minimises the norm. For the converse, assume there exists x \in K: \langle x-x^*, x^* -p \rangle \leq 0. Then x_\epsilon = (1- \epsilon ) x^* + \epsilon x \in K can take a negative value of the distance difference for small enough \epsilon:

2 \langle x_\epsilon-x^*, x^* -p \rangle + \|x_\epsilon-x^*\|^2 = \epsilon \langle x-x^* , x^* - p\rangle + \epsilon^2 \|x-x^*\|^2

Finally, we can verify that w := x^* - p gives a separating hyperplane:

\langle p-x^*, w \rangle = -\|p - x^*\|^2 <0

We also have that for all x \in K, \langle x-x^*, x^* -p \rangle \geq 0

Combining the two we get:

\langle p-x^*, w \rangle < 0 \leq \inf_x \langle x-x^*, x^* -p \rangle

\langle p, w \rangle < \langle x^*, w\rangle \leq \inf_x \langle x, w \rangle

A similar result for sets also exists: if we have closed convex C, D \subseteq \mathbb R^n, if they’re disjoint and one of them is bounded, then there is a separating hyperplane (w, b) \in \mathbb R^{n+1} satisfying:

\sup_{x \in C} \langle w, x \rangle < b < \inf_{x \in D} \langle w, x \rangle

Proof:

There is a hyperplane separating C and D iff there’s a hyperplane separating K = C-D and p=0. In order for K to be closed we need boundedness of one of them.

A convex set can be defined using the entire collection of support functions and corresponding hyperplane:

K = \{x \in \mathbb R^n: \forall w \in \mathbb R^n: \langle w, x\rangle \leq \sup_{y \in K} \langle w, y\rangle = h_K(w)\}

2.3.1 Suppporting hyperplane

A supporting half space H of K \subseteq \mathbb R^n at x \in \partial K satisfies:

1. K \supseteq H
2. x \in \partial H

For every closed convex K, and x \in \partial K, there is a supporting hyperplane H \supseteq K such that x \in \partial H.

If K \subseteq \mathbb R^n is closed with a non-empty interior, then K is convex iff it has a supporting hyperplane at each point in its boundary.