I do not know much about this subject, but I am trying to learn a little.

In a book I have it says that a primal problem is:

max $c'X$

subject to

$AX \ge b$

$X \ge 0$

It says that the dual of this is:

maximize $b'Y$

subject to:

$A'y \le c$

$Y \ge 0$

However they did not prove the linear programming duality theorem.

However I found another text where they do this, but there they use that:

max $c'X$

$AX \le b$

Has a dual

min $b'Y$


$y \ge 0$

Notice that in the third last onee I do not have a restriction on X, and in the last one we have an equality not an inequality, are these two representations equal? Is it a way to prove they are?

  • $\begingroup$ Are the links posted here helpful? $\endgroup$ – user147263 Aug 17 '14 at 21:38
  • $\begingroup$ It's useful to know the general dual problem construction in convex optimization, which is presented in Boyd and Vandenberghe for example. You can use it to derive dual problems for linear programs. $\endgroup$ – littleO Aug 18 '14 at 21:14

You can check out the following table. enter image description here

If the restrictions have the relation sign $\geq $ in the max-problem, then the dual-variables (min-Problem) has to be $y\leq 0$ (row 8 of the table)

And it should be $A'y\geq c$, because $x \geq 0$ (row 9 of the table)


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.