Past exam of the Probability, statistics and options II course of the University of Oxford / 2010 / T / T2 / a

The dual is $\boxed{\min b^{T}y\text{ subject to }{A}^{T}y\ge c,y\ge 0}$. Weak duality states that every primal feasible $x$ and dual feasible $y$ satisfy $c^{T}x\le b^{T}y$. Indeed,using $x\ge 0$ for the first inequality and $y\ge 0$ for the second. Thus a feasible dual value is an upper bound on every primal objective value, and a feasible pair with equal values certifies both optima.

For feasible points the duality gap decomposes asEach term in both sums is nonnegative. Therefore the gap is zero exactly when every product vanishes, namely the two sets of complementary slackness equations in the question (with $b-Ax$ or its negative making no difference to a zero product). If the equations hold, equality and weak duality prove optimality of both points. Conversely, if both are optimal and the optimal values are equal as assumed, the gap is zero, forcing each product to vanish. This proves both directions.

Try the dual intersection $3y_1+2y_2=6$, $y_1+4y_2=4$. It gives $y=(8/5,3/5)$; the remaining constraint is $5y_1+y_2=43/5\ge 5$, so it is dual feasible. Its strictly positive slack in the first column suggests $x_1=0$, while positivity of both $y$ entries suggests $Ax=b$. Solving $3x_2+x_3=1$, $2x_2+4x_3=2$ gives $x=(0,1/5,2/5)$, which is primal feasible.

Their objective values agree:Weak duality certifies that both are optimal. The strict first-column dual slack and the two active primal equations also show uniqueness of the primal optimum; positivity of $x_2,x_3$ forces the two dual equations, so the dual optimum is unique as well.