1  Convexity

1.1 Convex sets

Definition 1.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 1.2 (Span) \text{span}(S) := \left\{ \sum_{i=1}^N a_i x_i: x_i \in S \right\}

Definition 1.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 1.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)

1.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\}

1.2 Convex functions

Definition 1.5 (Convex function) 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.

1.2.1 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