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

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.