Find the dual of the following linear program 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!
 A: 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*}
