Certificate

From Glossary

Jump to: navigation, search
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.


Views
Personal tools