Linear programming duality and certificates

Consider maximizing $c^Tx$ subject to $Ax\le b$ and $x\ge0$. A nonnegative weight vector $y$ gives $y^TAx\le y^Tb$. If $A^Ty\ge c$, multiplying that inequality componentwise by $x\ge0$ also gives $c^Tx\le y^TAx$. Hence $b^Ty$ is an upper bound for every primal feasible objective. The dual minimizes this upper bound subject to the two conditions just used. Equality constraints would give unrestricted multipliers; unrestricted primal coordinates would require dual equalities. Signs follow from the bound proof rather than a memorized recipe.

Weak duality requires only feasibility and elementary inequalities. If a primal feasible point and a dual feasible point have equal objective values, both are optimal immediately. If their values differ, the nonnegative gap quantifies how far the primal point could still be from optimality. A small gap is meaningful only when feasibility has also been assessed: two infeasible vectors can have identical objective values. For floating-point results, include residual bounds or exact rational reconstruction when a formal certificate is needed rather than treating a printed gap as self-authenticating.

For a finite-dimensional linear program, if the primal is feasible and has a finite optimal value, an optimal primal solution exists and the dual also has an attained optimum with the same value. Strict feasibility is not required for this LP theorem. An unbounded primal forces dual infeasibility by weak duality. However, primal infeasibility alone does not force dual unboundedness: both programs can be infeasible. Always state which feasible side is known before drawing an implication. Feasibility, finite optimality, and unboundedness are different statuses, not interchangeable failure messages.

A useful exact alternative applies to the equality system $Ax=b$, $x\ge0$. Either such an $x$ exists, or there is a vector $y$ with $A^Ty\ge0$ and $b^Ty<0$, but never both. Indeed, simultaneous existence would imply $b^Ty=x^TA^Ty\ge0$, a contradiction. The existence of a separating certificate when the system is infeasible is Farkas' lemma. Notice that the certificate multiplier is unrestricted in sign here because the original restrictions are equalities. A different primal form needs a correspondingly different certificate.

An unboundedness certificate needs both a feasible base point and an improving recession direction. In our maximization form, require $x_0\ge0$, $Ax_0\le b$, $d\ge0$, $Ad\le0$, and $c^Td>0$. Then $x_0+td$ remains feasible while its value grows without limit. A direction alone cannot prove unboundedness if the original region is empty. Likewise, a dual vector certifies a bound only after every dual inequality and sign restriction is verified. These details make certificates short enough to audit without rerunning the optimization algorithm.

With rational input, exact arithmetic can verify a supplied rational certificate using finitely many additions, multiplications, and comparisons. This does not imply that all optimization problems are easy to solve: integer programming can have a strong continuous bound yet a hard combinatorial search. Even within linear programming, the conditioning and encoding size affect numerical algorithms. The dual perspective gives a useful workflow: propose a feasible decision, construct a bound from prices, compare their objectives, and investigate the remaining gap rather than trusting the first solver status line.