# Certificate

A set of sufficient conditions for some property to hold.

A certificate of optimality is a set of conditions that certify some feasible solution, $LaTeX: x$, is optimal. One example comes from duality: let $LaTeX: y$ be feasible in any dual with objective value $LaTeX: F(y)$. Then, $LaTeX: F(y)=f(x)$ is a certificate of optimality. In particular, if we have a linear program:

$LaTeX: \max \{ cx : Ax = b, x \ge 0,$

a certificate that a feasible $LaTeX: x$ is optimal is the set of dual conditions:

$LaTeX: A^Ty \ge c \;\;\mbox{ and }\;\; c^Tx = y^T b.$

(Note the general use of duality does not require any convexity assumption, and the dual can be weak.)

A certificate of unboundedness is a collection of conditions that certify a mathematical program is unbounded. An example from duality is that a primal feasible solution is found and the dual is determined to be infeasible. In particular, if we have a linear program:

$LaTeX: \max \{cx : Ax = b, \; x \ge 0 \},$

a certificate that this is unbounded is the existence of a feasible x and the determination that $LaTeX: A^Ty \ge c$ implies a contradiction.

A certificate of infeasibility is a set of conditions that certify a mathematical program is infeasible. One class comes from duality: a dual sequence is found whose objective diverges. In particular, if we have a linear program:

$LaTeX: \max \{ c^T x : Ax = b, \; x \ge 0\},$

then a certificate that this is infeasible is the existence of a sequence $LaTeX: y^k$ such that $LaTeX: A^T y^k \ge c$ for all $LaTeX: k$ and $LaTeX: y^k \rightarrow \infty$ as $LaTeX: y \rightarrow \infty$.