Cfrgtkky

Definition 1: Given linear programming problem (LP) $maxleft{left langle c,xright rangle| Ax=b, x
geq 0right}$. Then its dual is $minleft{left langle b,u right
rangle | A^Tu geq cright}$

Definition 2: Given (LP) $maxleft{left langle c,x right rangle |
A_1x=b_1, ,, A_2x leq b_2, ,, x geq 0right}$. Then its dual is
$minleft{left langle begin{pmatrix} b_1\ b_2 end{pmatrix},
begin{pmatrix} v\ w end{pmatrix} right rangle | A_1^Tv + A_2^Tw
geq c, ,, w geq 0right}$

I'm trying to show that both definitions are equivalent but I don't know how to do it? If I look at both, the only slight difference seems to be that in Def 1 you have a whole matrix $A$ but in Def 2 you have several submatrices $A_1, A_2$ that will form one matrix together (probably the same one as in Def 1.

But really no idea how this can be "shown"..? : / Maybe it's sufficient to choose an example and apply both definitions on it and if you get the same result, it's equivalent? Or this is not enough to "show" something?

Given a maximization problem of the form in definition $1$. Let us try to convert it into a maximization problem in the second form, and check the duality form definition $2$ is the same as duality in definition $1$.

We let $A_1=A$, $b_1=b$, $A_2=0$, $b_2$ be any nonnegative vector, then the dual accoding to Definition $2$ is

$$minleft{left langle begin{pmatrix} b_1\ b_2 end{pmatrix},
begin{pmatrix} v\ w end{pmatrix} right rangle | A_1^Tv + 0^Tw
geq c, ,, w geq 0right}$$

Also recall that $b_2$ is nonnegative and letting $w$ taking any positive value would only increases the objective function of the minimization problem. Hence the optimal $w$ must take value $0$. Hence it reduces to the dual in the first definition.

Similarly, given a maximization problem of the form in definition $2$. Let us try to convert it into a maximization in the form of the first definition by introducing slack variable $s$.

$$maxleft{left langle c,x right rangle |
A_1x=b_1, ,, A_2x leq b_2, ,, x geq 0right}\=maxleft{left langle begin{pmatrix}c\0 end{pmatrix},begin{pmatrix}x \send{pmatrix} right rangle |
begin{pmatrix}A_1 & 0 \ A_2 & Iend{pmatrix}begin{pmatrix}x \ send{pmatrix}=begin{pmatrix}b_1 \ b_2 end{pmatrix} ,, begin{pmatrix}x \send{pmatrix} geq 0right}$$

Now, we use the dual in the first definition, we obtain

$$minleft{left langle begin{pmatrix}b_1\b_2 end{pmatrix},begin{pmatrix}v \wend{pmatrix} right rangle |
begin{pmatrix}A_1^T & A_2^T \ 0 & Iend{pmatrix}begin{pmatrix}v \ wend{pmatrix}gebegin{pmatrix}c \ 0 end{pmatrix} right}$$

which is equivalent to the dual stated in definition $2$.