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

The dual is $\boxed{D:\min b^{T}y\text{ subject to }{A}^{T}y\ge c,y\ge 0}$. For feasible points $c^{T}x\le y^{T}Ax\le y^{T}b$, so its feasible objectives bound the primal objective from above. This is weak duality with the given maximization convention.

Feasibility makes both sums $x^T(A^{T}y-c)$ and $y^T(b-Ax)$ nonnegative. Their sum is the gap $b^{T}y-c^{T}x$. At optimal points the assumed equal optimal values make that gap zero, forcing each nonnegative sum to vanish. HenceIn fact every individual nonnegative product in the two sums vanishes, giving the componentwise complementary slackness conditions too.

Take the dual vector $y=(8/17,45/17{)}^T$. Its column constraints have values $5,12,53/17,233/17$, exceeding or equaling $c=(5,12,2,5{)}^T$; its entries are positive. Thus it is dual feasible. The first two constraints are equalities while the last two have strictly positive slack, suggesting $x_3=x_4=0$. Solve the two primal equalities to get $x_1=5/17$, $x_2=3/17$, both positive.

The resulting feasible objectives agree:Weak duality proves optimality. Strict dual slack in columns three and four and positive dual entries force the two primal equalities, proving primal uniqueness; positive first two primal coordinates force the two independent dual equalities, proving dual uniqueness.