I'm working on a HW assignment as follows:

Given the primal canonical problem: $$\min \langle c,x \rangle \quad \text{s.t}: Ax \geq b, x \geq 0$$ and the dual canonical problem: $$\max \langle b,y \rangle \quad \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,\dots,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^T y = (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?


closed as off-topic by Jack D'Aurizio Mar 13 '18 at 17:11

  • This question does not appear to be about math within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.