0
$\begingroup$

This is from a pdf file I found linked to from this site:

They first define the primal dual problem like this:

enter image description here

Then they have another representation of (p), and show that it's dual is:

enter image description here

Now here are my questions:

I understand what they did. But lets day they started with that the primal problem was unrestricted(x can be whatever), and then want to show that the corresponding dual has restriction equality($\pi A = c$). I read that you then can write $U,V \ge 0$ and $X = U-V$ and do a similar procedure to show this. I've tried but I get stuck, does anyone see how to do this procedure?

Here is my attempt:

max $cx$

$Ax \le b$

this is equal to

max $c(U-V)$

$A(U-V) \le b$

$U \ge 0$

$V \ge 0$

And where do I go from here? I was trying to be creative and say that this again was equal to two separate problems:

max $cU$

$AU \le b/2$

$U \ge 0$

And

max $-cV$

$-AV \le /b/2$

$V \ge 0$

However I was not able to finish the argument(when I transform them to theor duals containing $\pi_1$ and $\pi_2$, I am not able to get what I want, I was not able to combine $\pi_1$ and $\pi_2$). Does anyone see how we are supposed to do this?

Thanks

$\endgroup$
0
$\begingroup$

Continuing from your primal problem in this form:

(P)

max $c(U−V)$

$A(U−V) \leq b$

$U \geq 0$

$V \geq 0$

it might help to see it as the following:

(P)

max $cU + (-c)V$

$\begin{bmatrix}A &-A\end{bmatrix}\begin{bmatrix}U\\V\end{bmatrix} \leq b$

$U \geq 0$

$V \geq 0$

The point here is that we're more explicitly separating $U$ and $V$ by making the coefficient of $V$ equal to $-c$ in the objective function as opposed to subtracting $V$ from $U$, and similarly in the list of constraints.

Now, using the transformation you gave from primal to dual:

(D)

min $\pi b$

$\pi A \geq c$

$\pi (-A) \geq -c$

$\pi \geq 0$

Does this help?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.