# Converting between (standard) primal to dual forms (LP)

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?

• 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. – Yuval Filmus Dec 19 '17 at 11:31
• 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? – CIsForCookies Dec 19 '17 at 12:34
• 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. – Yuval Filmus Dec 19 '17 at 14:05
• 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 – CIsForCookies Dec 19 '17 at 14:23
• Perhaps you should contact a TA, then. – Yuval Filmus Dec 19 '17 at 14:24