The duality gap is the distance from p to its convex envelope
Left: the value function p(u) — the best cost when the constraint is loosened by u. Right: the dual g(λ). They are two views of one object: g(λ) is the height at u = 0 of the highest line of slope −λ that stays under p. Drag the slider (or drag either plot).
p(u), the value function
convex envelope p★★
supporting line, slope −λ
one x ∈ X
p(0) — best integer cost
11
d★ = p★★(0) — best bound
9
The eight points, and the staircase they generate (table view)