weak duality

Work in Progress

Summary

Primal to dual

Primal itemDual item
constraint variable , free,
variable , free, constraint

Concept

Duality

  • a dual is a related problem that gives bounds on the primal problem
𝟘𝟘

Weak duality

  • for min primal, the dual provides a lower bound on the primal’s objective

min problem is larger than the max problem

𝟘𝟘

Equality certifies both optimal. It also implies an unbounded primal has infeasible dual, and vice versa.

For a max primal, each primal constraint creates a dual variable and each primal variable creates a dual constraint; the matrix transposes.

Pasted image 20261110023619.png

Thus the dual of with right-hand side is a minimization of subject to the corresponding relations. In the standard pair,