Show that the dual of $\min c^{T}x+d^{T}x^{'}$ and $\max a^{T}x+b^{T}x^{'}$ are equivalent

Question

Show that $(1)$ can be written in the form $(2)$

$(1)$ $\min c^{T}x+d^{T}x^{'}$

$\operatorname{s.t.}$

$Ax+Bx^{'}\geq a$

$Cx+Dx^{'}= b$ where $x, x^{'} \geq 0$ and

and

$(2)$ $\max a^{T}y+b^{T}y^{'}$

$\operatorname{s.t.}$

$A^{T}y+C^{T}y^{'}\leq c$

$By+Dy^{'}= d$ where $y,y^{'} \geq 0$

My idea:

The restrictions $(1)$ can be written in the form:

$\mathcal{P}(\begin{pmatrix} A & -B \\ C & D \\ -C &-D \end{pmatrix},\begin{pmatrix} -a \\ b \\ -b \end{pmatrix})$

Then the dual LP to $(1)$ can be written as:

$\max \begin{pmatrix} a & -b & b \end{pmatrix}^{T}(y, -y)$

$\operatorname{s.t.}$

$\begin{pmatrix} A & -B \\ C & D \\ -C &-D \end{pmatrix}^{T}(y,y^{'})=-\begin{pmatrix} c \\ d \end{pmatrix}$

But how do I get to writing this in the form of $(2)$

Any help is greatly appreciated.

Answer 1

Primal

min $c^{T}x + d^{T}x'$

s.t

$Ax+ Bx' \geq a$

$Cx + Dx' = b$

$x \geq 0$

$x' \geq 0$

and we can rewrite de primal problem

min $c^{T}x + d^{T}x'$

s.t

$Ax+ Bx' \geq a$

$Cx + Dx' \geq b$

$-Cx - Dx' \geq -b$

$x \geq 0$

$x' \geq 0$

Dual

max $a^{T}y +b^{T}y - b^{T}y''$

s.t

$A^{T}y +C^{T}y' - C^{T}y'' \leq c$

$B^{T}y +D^{T}y' - D^{T}y'' \leq d$

$y \geq 0$

$y' \geq 0$

$y'' \geq 0$

and we can rewrite the dual problem

$z = y' - y''$

max $a^{T}y + b^{T}z$

s.t

$A^{T}y +C^{T}z \leq c$

$B^{T}y +D^{T}z \leq d$

$y \geq 0$

z unrestricted

Answer 2

Your problem $(1)$ consists of minimizing $c^Tx + d^Tx^\prime$ under the conditions

\begin{equation} Ax + Bx^\prime \geq a \qquad (i.) \\ Cx + Dx^\prime = b \qquad (ii.) \end{equation}

Suppose $z = \min c^Tx + d^Tx^\prime$. I want to find a good valid lower bound for $z$.

If I multiply $(i.)$ by a posivite value $y$ and $(ii.)$ by a rational value $y^\prime$, I get

\begin{equation} Axy + Bx^\prime y \geq ay \qquad (i^\prime.) \\ Cxy^\prime + Dx^\prime y^\prime = by^\prime \qquad (ii^\prime.) \end{equation}

Summing up $(i^\prime.)$ and $(ii^\prime.)$ one has

\begin{equation} x(Ay + Cy^\prime) + x^\prime(By + Dy^\prime) \geq ay + by^\prime \end{equation}

Notice that \begin{equation} c^Tx + d^Tx^\prime \geq x(Ay + Cy^\prime) + x^\prime(By + Dy^\prime) \geq ay + by^\prime \end{equation} holds if and only if

\begin{equation} Ay + Cy^\prime \leq c \qquad (iii.)\\ By + Dy^\prime \leq d \qquad (iv.) \end{equation}

Therefore, the best lower bound for z is obtained by maximizing $ay + by^\prime$ such that $(iii.)$ and $(iv.)$ hold.

PS.: I did not worry of transposing the matrix at the right places but you can do it on your own and see that the reasoning holds.