= Conic primal-dual gap
{title2=$g=c^Tx-b^Ty$}
For a <feasible point> $x$ and a feasible <dual variable> $y$, <weak duality> follows from one identity:
$$
g=c^Tx-b^Ty=(Ax-b)^Ty\geq0.
$$
The inequality is the defining property of the <dual cone>. Every feasible pair therefore encloses the optimal <objective function> value:
$$
b^Ty\leq d_*\leq p_*\leq c^Tx.
$$
Both optima are finite when such a pair exists. Consequently,
$$
0\leq c^Tx-p_*\leq g,\qquad 0\leq d_*-b^Ty\leq g.
$$
These are absolute cost bounds, rather than bounds on distance to an optimizing <vector>. Zero gap certifies both optima immediately. A small positive gap bounds the remaining improvement even if no <strong duality> theorem has been invoked.
For the <nonnegative-orthant optimality certificate> example, $x=(2.9,0.2)^T$ is feasible and costs $3.3$. Pairing it with $y=(0,1,1)^T$ gives $g=0.3$, so its cost exceeds the optimum by at most $0.3$. Here the optimum is known to be $3$, and the bound is exact. Pairing the same $x$ with the weaker $r=1/2$ certificate gives $g=1.8$: a valid but less informative guarantee.
The identity assumes exact primal and dual feasibility. With a dual <linear-system residual> $r_d=c-A^Ty$, it becomes
$$
c^Tx-b^Ty=(Ax-b)^Ty+x^Tr_d.
$$
The second term has no guaranteed sign. Checking only a small <linear-system residual> and the cone <dot product> is insufficient when $\|x\|_2$ is large; a separate bound $|x^Tr_d|\leq\|x\|_2\|r_d\|_2$ follows from the <Cauchy-Schwarz inequality>. Approximate cone membership likewise needs a quantified correction before claiming a certificate.
For an exact arithmetic example, minimize $x$ subject to $x\geq10^9$. The point $x=10^9$ is optimal. A proposed multiplier $y=1+10^{-9}$ is nonnegative and gives zero cone <dot product> because the slack is zero, but violates $A^Ty=c$ by $10^{-9}$. Its purported lower bound is $10^9+1$, exceeding the optimum. The missing term $x^Tr_d=-1$ explains the failure.
Back to article page
