Separating Hyerplane Example

Nov 30 2016

p.49. Example 2.19: Separation of an affine and a convex set: Suppose \(C\) is convex and \(D\) is affine, i.e., \(D = \{F u + g | u ∈ \mathbb{R}^m\}\), where \(F ∈ \mathbb{R}^{n×m}\). Suppose C and D are disjoint, so by the separating hyperplane theorem there are \(a \neq 0\) and \(b\) such that \(a^\top x ≤ b\) for all \(x ∈ C\) and \(a^\top x ≥ b\) for all \(x ∈ D\). Now \(a^\top x ≥ b\) for all x ∈ D means \(a^\top F u ≥ b − aT g\) for all \(u ∈ \mathbb{R}^m\). But a linear function is bounded below on \(\mathbb{R}^m\) only when it is zero, so we conclude \(a^\top F = 0\) (and hence, \(b ≤ a^\top g\)).

A geometric way to look at this is to think of \(D\) as the range of the linear map \(F\) plus an offset vector \(g\), or the column space of a matrix \(F\) plus \(g\). The only way to draw a hyperplane in space that doesn't intersect \(D\) is for it to be parallel to \(D\), i.e. the normal vector \(a\) needs to be perpendicular to the column space of \(F\), which requires \(a\) to be in the left-null space of \(F\), so \(a^\top F = 0\). This and the requirement that \(a^\top F u ≥ b − a^\top g\) give a constraint on the legal choices of \(b\), i.e. \(b ≤ a^\top g\). Then we also have \(a^\top x \leq b \leq a^\top g\) for all \(x \in C\).