0
$\begingroup$

I know how to derive dual for normal LPs, but what if we are unlikely to have something like this:

maximize z
s.t.   z < 3y-2
       1 < y < 2

, where the constraints are not directly related to the objective but related indeed. In this case, how can we compute dual for it?

Currently, the way I solve it is to ignore the second constraint and convert the original one into:

minimize -z
s.t.   z < 3y-2
       1 < y < 2

Firstly, I have this Lagrangian:

$L(z,\lambda) = -z + \lambda (z-3y+2)$.

Then take derivative w.r.t. $z$, and set it to be $0$:

$\frac{\partial L}{\partial z} = -1 + \lambda = 0$.

Finally, plugging in $\lambda=1$ into Lagrangian, we have:

$g(\lambda) = L(z*, \lambda) = -3y+2$.

Even if $g$ is not a function in terms of $\lambda$, but let's just write it in this way. Then I don't what to do next.

Thank you very much!

$\endgroup$
  • $\begingroup$ Given the second inequality (on $y$), how can you manipulate the $z$ inequality to incorporate all the data? Meaning, what will be the explicit scalar bounds on $z$? $\endgroup$ – iarbel84 Nov 30 '20 at 16:58
  • $\begingroup$ I actually have no idea. Currenly, the way I handle this is just to firstly ignore the second constraint, and use normal Lagrangian. $\endgroup$ – Huimin ZENG Nov 30 '20 at 17:15
  • $\begingroup$ Then what happens when you construct a Lagrangian and try to derive a dual problem? $\endgroup$ – iarbel84 Nov 30 '20 at 17:38
  • $\begingroup$ let me show it in the original question $\endgroup$ – Huimin ZENG Nov 30 '20 at 17:59
1
$\begingroup$

Rewrite as:

maximize 0y + 1z
s.t.    -3y + 1z <= -2
        -1y + 0z <= -1
         1y + 0z <=  2

Then the dual is:

minimize -2t - 1u + 2v
s.t.     -3t - 1u + 1v = 0
          1t + 0u + 0v = 1
           t,   u,   v >= 0

Equivalently:

minimize -u + 2v - 2
s.t.     -u +  v = 3
          u,   v >= 0

Equivalently:

minimize  u + 4
s.t.      u >= 0

Hence $(t,u,v)=(1,0,3)$ is the unique optimal dual solution, and complementary slackness yields optimal primal solution $(y,z)=(2,4)$.

$\endgroup$
  • $\begingroup$ Oh! This is perfect! Thanks a lot! $\endgroup$ – Huimin ZENG Dec 1 '20 at 15:42
  • $\begingroup$ Glad to help. Please mark my answer as accepted. $\endgroup$ – RobPratt Dec 1 '20 at 15:46

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.