# Certificate

### From Glossary

A set of sufficient conditions for some property to hold.A certificate of optimality is a set of conditions that certify some feasible solution, , is optimal. One example comes from duality: let be feasible in any dual with objective value . Then, is a certificate of optimality. In particular, if we have a linear program:

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

(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:

a certificate that this is unbounded is the existence of a feasible x and the determination that 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:

then a certificate that this is infeasible is the existence of a sequence such that for all and as .