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$
2
$\begingroup$

As you mention, maximization and minimization problems are equivalent. Given a recipe for dualizing a minimization problem, you can convert it into a recipe for dualizing a maximization problem as follows:

  1. Negate the objective function and change the maximum to a minimum.
  2. Compute the dual.
  3. Negate the objective function and change the maximum to a minimum.

The new dual problem will have the same objective value as the primal one (under some mild conditions). This property easily follows from the same fact for duals of minimization problems.

If you're careful enough, you should also get that dualizing twice brings you back to the original program.

$\endgroup$

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.