Convex Optimization 2026, 32 - Distance Between Sets

The distance between sets C, D is defined as dist(C, D) = inf{||x - y|| : x ∈ C, y ∈ D}. If dist(C, D) > 0, they don't intersect, and if it's equal 0, they do. Also, dist(C, D) = dist(0, D - C). If C = {x : f_i(x) ≤ 0, i, ..., m}; D = {x : g_i(x) ≤ 0, i = 1, ..., p}, then dist(C, D) is determined by minimizing ||x - y|| where f_i(x) ≤ 0 and g_i(y) ≤ 0 (Eq. 8.3). This extends analogously to polyhedra (Eq. 8.4) (8.2.1). The dual of finding the distance between two convex sets is expressible through separation of hyperplanes between those sets. It minimizes ||ω|| with f_i(x), g_i(y) ≤ 0 and x - y = ω (Eq. 8.5). The resulting dual function is

which diverges for all ||z||_* > 1 toward -∞. This, too, extends directly to polyhedra (8.2.2). Using indicator functions, the distance between two convex sets minimizes ||x - y|| with I_C(x) ≤ 0; I_D(y) ≤ 0. The dual of this maximizes -S_C(-z) - S_D(z) with ||z||_* ≤ 1 (8.2.3).

Lengths, distances and angles can be expressed through a Gram matrix G = A^TA; A = [a_i... ], i.e. G_ij = a_i^Ta_j. Its diagonal entries can be considered to be known and fixed, and comprise the lengths l_i. The distances between a_i and a_j are d_ij = ||a_i - a_j||₂ = (l_i² + l_j² - 2G_ij)^1/2. Define the correlation coefficient

which defines the angles between as θ_ij = cos^-1ρ_ij. Due to its construction, G is symmetric and positive semidefinite (p. 406). Constraints can be imposed on the angle through its associated lengths l_il_jcos α ≥ G_ij ≥ l_il_jcos β for α ≥ θ_ij ≥ β. A similar constraint can be imposed on the distances (p. 407).