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

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.

Write $Ax=b$ as $Ax\le b$ and $-Ax\le -b$. The dual has nonnegative multipliers $u,v$ for these inequalities, with objective $b^{T}u-b^{T}v$ and condition $A^T(u-v)\ge c$. Every real vector $y$ can be expressed as $u-v$ with $u,v\ge 0$. HenceThe equality constraints remove the sign restriction on the dual variables.

The expression $G^{-1}$ presupposes that $G$ is invertible; positivity of the stated optimal coordinates alone would not prove that, so use the nonsingularity implicit in this expression. Let $c_B$ be the first $m$ components of $c$ and set $y=G^{-T}{c}_B$. Then $G^{T}y=c_B$.

For any nonbasic column $a_j$, introduce $x_j=\epsilon >0$ while changing the basic vector from $u$ to $u-\epsilon G^{-1}{a}_j$. This stays feasible for sufficiently small $\epsilon$ because every $u_i>0$. Optimality at $u$ implies the objective slope $c_j-c_B^T{G}^{-1}{a}_j\le 0$. Therefore $a_j^{T}y\ge c_j$ for every such column, and the basic columns satisfy equality. Thus $y$ is dual feasible, independently of the right-hand side.

For $v=G^{-1}{b}^{\ast }\ge 0$, the proposed $x^{\ast }$ is primal feasible andWeak duality, valid with unrestricted equality multipliers, proves $\boxed{x^{\ast }\text{ is optimal}}$. This also explains the stability of an optimal basis while its new basic coordinates remain nonnegative.