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

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.

Write each unrestricted coordinate as $x_j=u_j-v_j$ with $u_j,v_j\ge 0$. Then the primal has nonnegative variables $(u,v)$, constraint matrix $[A,-A]$, and objective coefficients $(c,-c)$. Its dual constraints are $A^{T}y\ge c$ and $-A^{T}y\ge -c$, hence equality. ThereforeThe removed sign restriction on the primal variables becomes equality of the dual column constraints.

The first two active constraints give $x_1+2x_2=4$, $3x_1+2x_2=6$, hence $x=(1,3/2{)}^T$. The remaining left side is $4+3/2=11/2<6$, so it is feasible, with objective $5/2$. The associated dual has $y\ge 0$ and equalities $y_1+3y_2+4y_3=1$, $2y_1+2y_2+y_3=1$. The vector $y=(1/4,1/4,0{)}^T$ is feasible and has value $4/4+6/4=5/2$. ThusEqual objectives certify both optima even with unrestricted primal variables. The positive first two dual entries force both active constraints at any primal optimum, so that optimum is unique. The positive slack in the third primal constraint forces $y_3=0$ at any dual optimum, and the two dual equalities then determine its unique value.