How can both these definitions be equivalent (duality)?

46 Views Asked by At

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

Definition 2: Given (LP) $\max\left\{\left \langle c,x \right \rangle | A_1x=b_1, \,\, A_2x \leq b_2, \,\, x \geq 0\right\}$. Then its dual is $\min\left\{\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 0\right\}$

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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

$$\min\left\{\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 0\right\}$$

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$.

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

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

$$\min\left\{\left \langle \begin{pmatrix}b_1\\b_2 \end{pmatrix},\begin{pmatrix}v \\w\end{pmatrix} \right \rangle | \begin{pmatrix}A_1^T & A_2^T \\ 0 & I\end{pmatrix}\begin{pmatrix}v \\ w\end{pmatrix}\ge\begin{pmatrix}c \\ 0 \end{pmatrix} \right\}$$

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