I am going over sample questions from a sample exam, and I got stuck on the following question. I need to determine the dual of this LP:
$min: c^Tx + d^Tu \\ s.t: Ax + Du = b\\ x \ge 0$
$A$ is an $m$ by $n$ matrix, D is an $m$ by $p$ matrix. So this is what is throwing me off when I try this question. I know that the dual of a regular LP like:
$min: c^Tx \\ s.t: Ax = b \\ x \ge 0$
becomes
$max: b^Ty \\ s.t: A^Ty \le c$
However, in this case, if I try applying the same type of strategy, I get stuck as follows:
$max: b^Ty \\ s.t: A^Ty + D^Ty \; (\le, =) (c, d)$
The problem is that the dimensions of $A^T$ and $D^T$ don't agree anymore... so I tried adding an extra set of dual variables $z$... but it doesn't really get me anywhere, since $b$ is a vector in $R^m$ so any dual variables would have to be of that dimension as well.
Any hints/suggestions?
You could try deriving it. I doubt you can use direct formulae for this case. (Just out of curiosity, is it a 2 stage Stochastic Programming Problem?) I present an explanation for a simpler case. \begin{align} \min &\quad c'x\\ Ax&=b\\ \end{align} In order to take the dual, you first take the Lagrangian. \begin{align} L(x;\lambda)&= c'x-\lambda '(Ax-b)\\ \nabla_xL(x;\lambda)&= c-A'\lambda=0\\ \end{align} Thus, we got the constraint for optimality- $A'\lambda=c$.
Now, objective function. \begin{align} L(x;\lambda)&= c'x-\lambda '(Ax-b)\\ L(x;\lambda)&= c'x-\lambda 'Ax+\lambda 'b\\ L(x;\lambda)&= (c-A'\lambda )'x+\lambda 'b\\ L(x;\lambda)&= 0'x+\lambda 'b\\ L(x;\lambda)&= \lambda 'b\\ \end{align} Now, for when we deal with the Langrangian, we have a $\max \min$ operator. Thus, the objective function is: \begin{align} \max_{\lambda} \min_x L(x;\lambda)&= \max_{\lambda} \min_x \lambda 'b\\ \max_{\lambda} \min_x L(x;\lambda)&= \max_{\lambda} \lambda 'b \end{align} That is all, we have our objective function : $\max_{\lambda} \lambda 'b$ and the constraint $A'\lambda=c$. You can work out the algebra along the same lines for your specific case, I don't think the results will be as clean (maybe they are).