# How to derive the dual for LP like this?

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!

• 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$? – iarbel84 Nov 30 '20 at 16:58
• I actually have no idea. Currenly, the way I handle this is just to firstly ignore the second constraint, and use normal Lagrangian. – Huimin ZENG Nov 30 '20 at 17:15
• Then what happens when you construct a Lagrangian and try to derive a dual problem? – iarbel84 Nov 30 '20 at 17:38
• let me show it in the original question – Huimin ZENG Nov 30 '20 at 17:59

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)$$.

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