= 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\ge0$, dual feasibility means $y\ge0$ and $A^Ty\ge c$. Hence
$$
c^Tx\le x^TA^Ty=y^TAx\le y^Tb.
$$
The first inequality uses $x\ge0$; the last uses $y\ge0$. 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.
Back to article page