2
$\begingroup$

I have it as a homework question to compare dual programs in the following way:

  1. Take a canonical program and write its dual
  2. Take the same canonical program, write it as a standard program, take the dual of the latter, then write it as a canonical program.

In the following image, option 1 is starting with the upper left square and going right, and option two is (starting with the same place and) going down and then right and then up.

enter image description here

I have tried to do this, both in general and both by example, but I'm getting something strange: First I add slack variables to move from inequalities to equality, and I add the constraint that all slack variables are positive.

Then I write the dual of that program, the inequality look like $[A|I]^Ty\leq [c|0]$

(here $[A|I]$ denotes a block matrix) which gives two sets of inequalities: one is $A^Ty\leq c$ and the other is $Iy\leq 0$. Which is almost like the CD form in the picture - but I got $y\leq 0$ instead of $y\geq 0$.

Why do I get a different result ? I guess I have some error and that I should actually get $y\geq 0$, but I checked multiple times and I don't see any errors.

$\endgroup$
2
$\begingroup$

Since $Ax\ge b$, you should make $Ax$ smaller to get equality. Slack variables are also non-negative, so the coefficients should be $-1$. It's $[A|-I]$ instead of $[A|I]$.

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