The Bound

The Bound Tightens

Weak duality gives many valid upper bounds, and some are sharper than others. This lesson compares several dual-feasible points. The final row reaches the dual optimum, where the upper bound becomes exact.

highlighted = computed this step

A coarse bound

The feasible point (1, 1) gives bound 8. Why: it is valid, but it overpays for the resources.

b⋅y=8b\cdot y=8
Tightening dual boundsDual-feasible bounds shrink until the optimal dual matches the primal value.dual point bound1181/21/241/31/38/3

A smaller bound

The feasible point (1/2, 1/2) gives bound 4. Why: moving through the dual feasible region can tighten the certificate.

b⋅y=4b\cdot y=4
Tightening dual boundsDual-feasible bounds shrink until the optimal dual matches the primal value.dual point bound1181/21/241/31/38/3

The tight bound

At (1/3, 1/3) the bound is 8/3, the same as the primal optimum. Why: the best dual bound is the exact certificate.

b⋅y∗=8/3b\cdot y^*=8/3
Tightening dual boundsDual-feasible bounds shrink until the optimal dual matches the primal value.dual point bound1181/21/241/31/38/3

Diagram note

Each row is a dual-feasible point and the exact bound recomputed from b dot y. Pixel positions are rounded for layout; every number shown is exact.

tight dual bound equals primal optimum\text{tight dual bound equals primal optimum}
Tightening dual boundsDual-feasible bounds shrink until the optimal dual matches the primal value.dual point bound1181/21/241/31/38/3