2.1 Convex sets and polyhedra
Definition 2.1.1. A set \(S \subseteq \mathbb R^n\) is convex if it contains the segment between any two of its points: \(x, y \in S\) and \(0 \leq \lambda \leq 1\) imply \(\lambda x + (1 - \lambda )y \in S\). A convex combination of \(x^1, \ldots , x^k\) is \(\sum \lambda _ix^i\) with \(\lambda _i \geq 0\) and \(\sum \lambda _i = 1\). A polyhedron is a set \(\{x : Gx \leq h\}\), the intersection of finitely many closed half-spaces.
A half-space \(\{x : g^{\mathsf T}x \leq \eta \}\) is convex, since \(g^{\mathsf T}(\lambda x + (1 - \lambda )y) = \lambda g^{\mathsf T}x + (1 - \lambda )g^{\mathsf T}y \leq \eta \), and an intersection of convex sets is convex. So every polyhedron, in particular the feasible region of every LP, is convex. The standard-form region \(P = \{x : Ax = b, x \geq 0\}\) is a polyhedron, since an equation is two inequalities.
Definition 2.1.2. A point \(x\) of a convex set \(S\) is an extreme point if it is not a convex combination of two other points of \(S\): \(x = \lambda y + (1 - \lambda )z\) with \(y, z \in S\) and \(0 < \lambda < 1\) implies \(y = z = x\). For a polyhedron, the extreme points are its vertices.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.