 Weak duality

Weak duality bounds every feasible primal objective by every feasible dual objective, with the direction set by the primal convention. For the primal maximization $Ax\le b$, $x\ge 0$, dual feasibility means $y\ge 0$ and $A^{T}y\ge c$. HenceThe first inequality uses $x\ge 0$; the last uses $y\ge 0$. For a minimization primal, feasible dual values instead provide lower bounds. The argument is algebraic and needs no assumption that optima exist or are equal.

If a feasible pair attains equal objective values, each side must already be optimal. If a maximization primal is unbounded above, no feasible finite-valued dual vector can exist. The converse of that last statement is not automatic: dual infeasibility can also occur when the primal is infeasible. Strong duality is the additional theorem asserting equality under suitable conditions.