3
$\begingroup$

Suppose we have a primal problem $P$ which is stated as a maximization problem $\max c^{T} x$.

The dual problem is defined (Introduction to Linear Optimization by Dimitris Bertsimas) only for a primal minimization problem.

Then what is the dual problem of $P$ ?

Is it implicit, that the dual problem of $P$ is the dual problem of $P$ stated as the minimization problem $\min -c^T x$ ?

Surely these two primal problems are equivalent in the sense that their optimal solution $ \bar x$ are equal (if it exist). However, the objective values are the same only if we ignore the sign !

$\endgroup$
1
  • $\begingroup$ The dual problem of P should have dual variables. And where are your constraints ? $\endgroup$ Commented Nov 14, 2014 at 11:24

1 Answer 1

2
$\begingroup$

I do not have the book of Bertsimas in front of me, but it should state somewhere that "the dual of the dual is again the primal".

So, concerning your question the dual of a $\max$ problem is a $\min$ problem without any need to transform the $\max$ firstly to a $\min$ and then take the dual.

If you insist transforming first to a $\min$ problem and then taking the dual, then it is correct (as you say) that $$\max c^Tx=-\min(-c^T)x$$ so the objective value will be the same but with opposite signs.

$\endgroup$
9
  • $\begingroup$ The book doesn't say what you are saying, however it says: "If we transform the dual into an equivalent minimization problem and then form its dual, we obtain a problem equivalent to the originial problem" - can you say something about this :) ? $\endgroup$
    – Shuzheng
    Commented Nov 14, 2014 at 11:34
  • $\begingroup$ I found the book online. The dual of the dual is again the primal, that is what you should keep in mind. Wikipedia (en.wikipedia.org/wiki/Linear_programming#Duality)starts with a maximization problem as primal. It is the same. Table 4.1 in Bertsimas p. 143 can be used for both directions. You can start from second column and go to the first or from the first and go to the second. $\endgroup$
    – Jimmy R.
    Commented Nov 14, 2014 at 11:46
  • $\begingroup$ Ahh, under the table 4.1 you are refering too, it says "If we start with a maximazation problem, we can always convert it into an equivalent minimization problem, and then form its dual according to the rules we have just described". I guess, they don't explain the dual of the dual is again the primal, by means of their definition of the dual and to avoid confusion. Do you think I'm right ? Thanks for your help ! $\endgroup$
    – Shuzheng
    Commented Nov 14, 2014 at 11:57
  • $\begingroup$ Yes, as you say they do not explain it as the dual of the dual, but I think they should have done it, since it is an important simplification and it does not cause confusion! Primal - dual is reflexive (hope this is the correct word) and that causes no confusion. On the contrary their approach with the transformation causes some confusion IMO, but certainly they know much more. I think they refer mainly to engineers and perhaps it serves better their scope that way. Did you check the Wikipedia link to confirm it? $\endgroup$
    – Jimmy R.
    Commented Nov 14, 2014 at 12:02
  • $\begingroup$ Yep, so in general we can go both ways, that is take the dual of a maximzation problem and obtain the same theory. Can you recommend a better book turned towards mathematicians ? $\endgroup$
    – Shuzheng
    Commented Nov 14, 2014 at 12:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .