[Math] Dual problem of a maximization primal problem $P$

linear programming

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 !

Best Answer

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.

Related Question