It is known that in Linear Programming the Dual of the Dual is the Primal.
In wikipedia I saw that apart from the symmetric Dual I knew, there is also the asymmetric one: https://en.wikipedia.org/wiki/Dual_linear_program#Vector_formulations
I tried to show that the "Dual of the Dual is the Primal" would still hold in this case but I didn't manage to.
My question is: Does the "Dual of the Dual is the Primal" still holds for the asymmetric case? And if yes, could you please provide a comprehensive proof ?
Okey. I managed.
The asymmetric duality says:
Primal
max ${c^Tx}$
s.t. $Ax ≤ b$
produces the folowing
Dual
min $b^Ty$
s.t. $A^Ty = c$
$y ≥ 0$
I want to prove that I can go back to Primal from the Dual applying only the knowledge of this asymmetric transformation.
First I need to bring the Dual in the 'standard' form as in Primal:
$$ max\; -b^Ty\\ s.t.\quad \begin{align} A^Ty & \le c\\ -A^Ty & \le -c\\ -y & \le 0\\ \end{align}\\ $$ $$ \implies \begin{align} max\; -b^Ty\\ s.t. \qquad \begin{bmatrix}A^T\\-A^T\\-I\end{bmatrix} \begin{bmatrix}y\\y\\y\end{bmatrix} = \begin{bmatrix}c\\-c\\0\end{bmatrix} \end{align} $$ Where $I$ is the identity matrix. Applying the assymetric Dual transformation we get: $$ min\; \begin{bmatrix}c^T & -c^T & 0\end{bmatrix}w\\ s.t. \begin{align} \quad \begin{bmatrix}A & -A & -I\end{bmatrix}w & = -b\\ w & \ge 0 \end{align}\\ $$ let $w = \begin{bmatrix}u & v & k\end{bmatrix}^T$. Then: $$ min\; c^Tu -c^Tv\\ s.t. \begin{align} \quad Au -Av -Ik & = -b\\ u,v,k & \ge 0 \end{align}\\ $$ reforming: $$ max\; c^T(v - u)\\ s.t. \begin{align} \quad A(v - u) & = b - Ik\\ u,v,k & \ge 0 \end{align}\\ $$ let $x = v-u$ $$ max\; c^Tx\\ s.t. \begin{align} \quad Ax & = b - Ik\\ k & \ge 0 \end{align}\\ $$ We no longer have guarantee for the sign of $x$.
Since $k \ge 0$ the Right Hand Side will be greater if we omit the last term: $$ max\; c^Tx\\ s.t. \begin{align} \quad Ax \le b \\ \end{align}\\ $$ Which is exactly the Primal Problem.