Convex Optimization 2026, 05 - Separating and Supporting Hyperplanes

Hyperplanes can be used to separate nonintersecting convex sets. Section 2.5.1. of the book opens with a proof of the separating hyperplane theorem. The theorem states that for two nonintersecting convex sets C, D there is exists an a ≠ 0, b: a^Tx ≤ b ∀ x ∈ C ∧ a ^Tx ≥ b ∀ x ∈ D. This is equivalent to stating that the affine function a^Tx - b is nonpositive on C and nonnegative on D (2.5.1, p. 1). Strict separation of C and D uses strict inequalities. The converse of the separating hyperplane theorem is not generally true, but if C is open and there is an affine function f that is nonpositive on C and nonnegative on D, then they are disjoint (2.5.1).

Given C ⊂ ℝⁿ, x₀ in a point in its boundary ∂C, if a ≠ 0 with a^Tx ≤ a^Tx₀ ∀ x ∈ C, then {x | a^Tx = a^Tx₀} is a supporting hyperplane to C at x₀. x₀ then, is separated from C by that supporting hyperplane. Geometrically, the supporting hyperplane is tangent to C at x₀, where the halfspace {x | a^Tx ≤ a^Tx₀} contains C. The supporting hyperplane theorem states that for nonempty convex sets C and x₀ ∈ ∂C, there exists a supporting hyperplane to C at x₀. If a set is closed, has nonempty interior and a supporting hyperplane at every point in its boundary, it's convex. (2.5.2.)