= Robust infeasibility under uniform constraint relaxation
{title2=$\varepsilon<1/\sum_i\lambda_i$}
Suppose a <linear program> has a <Farkas' lemma> certificate $\lambda\geq0$, $A^T\lambda\geq0$, $b^T\lambda=-1$. A purported <feasible point> of $Ax\leq b+\varepsilon\mathbf1$, $x\geq0$ would imply $0\leq\lambda^TAx\leq-1+\varepsilon\sum_i\lambda_i$. Hence every relaxation below the displayed positive threshold remains infeasible. For rational inputs, bounds on the encoding length of a certificate supply the precision gap used by the <ellipsoid method>.
Back to article page
