| | CERTIFICATECertificate - This is a set of sufficient conditions for some property to hold. Certificate of optimality consists of conditions that certify some feasible solution, x, is optimal. One class of comes from duality: let y be feasible in any dual with objective value F(y). Then, F(y)=f(x) is a certificate of optimality. In particular, if we have an LP : max cx: Ax = b, x >= 0, a certificate that a feasible x is optimal is the set of dual conditions: yA >= c and cx=yb. (Note the general use of duality does not require any convexity assumption, and the dual can be weak .) Certificate of unboundedness consists of conditions that certify a mathematical program is unbounded. One class comes from duality: a primal feasible solution is found and the dual is determined to be infeasible. In particular, if we have an LP : max cx: Ax = b, x >= 0, a certificate that this is unbounded is that we found feasible x and determined yA >= c implies contradiction. Certificate of infeasibility consists 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 an LP : max cx: Ax = b, x >= 0, a certificate that this is infeasible is that we found a sequence (yk) such that ykA >= c for all k and (yk b) ––> –  . Also, see the supplement, Alternative Systems . | |
