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:
- $b = Ax$
- $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?