1
$\begingroup$

I have LP of the form min $c^tx$ such that $Ax\leq b$, there is no restricition on $x$.

I need to show the dual of the dual of this LP is the original LP.

To get the dual of my LP, I need to put it first into a maximization problem.

  1. My LP is equivalent to max $-c^tx$ such that $Ax\leq b$.
  2. Dualise this to get min $b^ty$ such that $A^ty=-c$ and $y\geq 0$
  3. Turn this into a maximization problem : max $-b^ty$ such that $A^ty=-c$ and $y\geq 0$.
  4. Into standard inequational form this is : max $-b^ty$ such that $A^ty\leq -c$.
  5. Dualise this : min $-c^tw$ such that $(A^t)^tw=-(b^t)^t$ and $w\geq 0$
  6. That is, min $-c^tw$ such that $Aw=-b$ and $w\geq 0$.
  7. Or min $-c^tw$ such that $Aw\leq-b$

Which is quite different from the original LP. Where are my mistakes ? I think I am confused when I go from a minimization problem to a minimization problem. In the lecture we have seen we can go from a minimization problem min $c^tx$ to maximization problem by maximizing $-c^tx$. But what happens to the inequality $Ax\leq b$ ?

This question have been asked before but I did not understand the explanation, the technique is different I think. Thanks !

$\endgroup$
8
  • 1
    $\begingroup$ 3 to 4 and 6 to 7 are completely wrong. Take $A^t=1$, $-c=1$. So $y=1$ is no way to give $y\le 1$. $\endgroup$ – A.Γ. Nov 8 '15 at 10:46
  • $\begingroup$ I see, thanks ! How do you go from a minimization problem to a maximization probme then ? $\endgroup$ – ALM Nov 8 '15 at 10:48
  • $\begingroup$ You need to find the correct dual set to the one given by "equalities+positivity" using the definition of a general dual (I do not know how it is given in your lectures it may be done by several ways, producing the same result). $\endgroup$ – A.Γ. Nov 8 '15 at 10:51
  • $\begingroup$ The definition of the dual is given only for a maximization problem though. Would I get max $-c^tx$ such that $(A^t)^tw=-(b^t)^t$ and $w \geq 0$, i.e. step 5 ? That means I would just get the first dual into standard inequational form and then dualise straight away again ? $\endgroup$ – ALM Nov 8 '15 at 10:56
  • $\begingroup$ One approach is to "standardize" the set, i.e. to rewrite equalities as inequalities and get rid of positivity via the standard substitution. After that use the standard dualization rule. It is messier, I do not like it. The second approach is to construct the dual set by using the general rules (see, for example, this lecture, Section 4.4, page 141). $\endgroup$ – A.Γ. Nov 8 '15 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.