Let $A$ be a real $m \times n$ matrix, and $l, u$ be two column vectors with length $n$. Suppose also that $m < n$. Find the dual of the linear program
min $c^Tx$ st $Ax = b$ and $l <= x <= u$
I got stuck so badly of the last constraints on $x$. Please give me some hints. Thanks!
First form the Lagrangian of the problem: $$ L(x,\lambda,\mu,\nu) := c^Tx - \lambda^T(Ax-b) - \mu^T (x-l) - \nu^T(u-x) $$ where $\lambda$ is the vector of dual variables associated with the constraint $Ax-b = 0$, $\mu$ the vector of dual variables associated with the constraints $x -l\geq 0$ and $\nu$ the vector of dual variables associated with $ u - x\geq 0$. Recall that since the latter two constraints are inequalities, the dual variables are required to be non-negative.
The dual problem is defined as: $$ \sup_{\lambda, \mu\geq 0, \nu\geq 0}\inf_{x} L(x,\lambda,\mu,\nu). $$ Define the dual function as: $$ g(\lambda, \mu, \nu) := \inf_{x} L(x,\lambda,\mu,\nu). $$ We have: $$\nabla_x L (x, \lambda, \mu, \nu) =c - A^T\lambda - \mu +\nu$$ It follows that $g$ is unbounded unless $c - A^T\lambda - \mu +\nu =0$, in other words: $$ g(\lambda, \mu, \nu)=\begin{cases} \lambda^T b + \mu^Tl - \nu^T u,& \text{if }c - A^T\lambda - \mu +\nu =0\\ -\inf,&\text{else} \end{cases}. $$ Consequently, we find that the dual problem reads: \begin{align*} \sup~ & \lambda^T b + \mu^Tl - \nu^T u,\\ s.t.~& A^T\lambda + \mu - \nu =c\\ & \mu\geq 0, \nu\geq 0 \end{align*}
