0
$\begingroup$

I'm working on a HW assignment as follows:

Given the primal canonical problem: $$min \langle c,x \rangle \text{ s.t. } Ax \geq b, x \geq 0$$ and the canonical dual problem: $$ max \langle b,y \rangle \text{ s.t. } A^Ty \leq c, y \geq 0$$

Show that converting PC (primal canonical) to DC (dual canonical) is similar when done directly or when done via canonical to standard conversion (i.e. primal canonical -> dual canonical == primal canonical -> primal standard -> dual standard -> dual canonical).

I converted the CP to SP (standard primal) by adding slack variables $s_1,\ldots,s_n\geq 0$ and adding them to each inequality.

My problem is showing the similarity between the SP and SD (standard dual).

What I've done so far is this: SD (standard dual) wants to maximize $b^Ty$ so:

  1. $b = Ax$
  2. $b^ty = (Ax)^Ty = (x^TA^T)y = x^T(A^Ty) \leq x^Tc$

Now, I don't know how to proceed. How can I show that minimizing $c^Tx$ is maximizing $b^Ty$? Am I on the correct path?

PS: I am pretty sure dual and primal problems can be shown where the primal is max and the dual is min, but I think it doesn't matter at all, right?

|cite|improve this question
$\endgroup$
  • $\begingroup$ How can I show that minimizing $c^Tx$ is maximizing $b^Ty$? This is strong duality. It's a deep property of linear programs. I think you're missing the point of this exercise: they want you to show that several different syntactic manipulations lead to obviously equivalent LPs. $\endgroup$ – Yuval Filmus Dec 19 '17 at 11:31
  • $\begingroup$ I don't follow. The strong duality says the optimum of dual and primal problems (if exists) is equal, so I should use the theorem to move between dual and primal forms? Where the slack variables (standard vs. canonical forms) take their place in this? $\endgroup$ – CIsForCookies Dec 19 '17 at 12:34
  • $\begingroup$ You're not supposed to reprove duality. You're supposed to do the syntactic manipulations in two different ways, and to show that you obtain equivalent programs. The first way is to convert directly, and the second way is via the canonical to standard conversion. $\endgroup$ – Yuval Filmus Dec 19 '17 at 14:05
  • $\begingroup$ Ok, but what is the meaning of this conversion? I don't see any implication for having or not having the slack variables, so from my perspective, I just know (due to reading the theorem) the forms are equal - I don't know how to split the "jump" between the forms to smaller steps $\endgroup$ – CIsForCookies Dec 19 '17 at 14:23
  • $\begingroup$ Perhaps you should contact a TA, then. $\endgroup$ – Yuval Filmus Dec 19 '17 at 14:24
2
$\begingroup$

In class you have been shown several algorithms:

  • Algorithm A: Convert a primal canonical to a dual canonical.
  • Algorithm B: Convert a primal canonical to a primal standard.
  • Algorithm C: Convert a primal standard to a dual standard.
  • Algorithm D: Convert a dual standard to a dual canonical.

Notice that if you run Algorithms B,C,D in sequence, then you get another algorithm for converting a primal canonical to a dual canonical. The question is to compare the dual canonical program constructed this way to the one constructed by applying Algorithm A.

|cite|improve this answer
$\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.