Dual of a Linear Program

Question

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align} Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by \begin{align} \max_{\lambda} \lambda^Tb \\ s.t.~\lambda^TA\leq c^T \end{align}

But in the constraint, I always get an equality (using what I learnt) \begin{align} \max_{\lambda} \lambda^Tb \\ s.t.~\lambda^TA = c^T \end{align} Please give some explanation also.

Answer 1

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align}

Is the same as: \begin{align} \min_{x} c^T(x^+-x^-) \\ s.t.~A(x^+-x^-)=b\\ x^+,x^-\geq 0 \end{align} Is the same as: \begin{align} \min_{x} [c^T|-c^T]z \\ s.t.~[A|-A]z=b\\ z\geq 0 \end{align} $$z=[x^T|-x^T]^T$$ Dual of this is : \begin{align} \max \quad b^Tp\\ s.t. [A|-A]^Tp\leq [cT|-c^T]^T\\ \implies Ap=c \end{align} I think your answer is correct.

Answer 2

Given

$\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align}$

I think the dual of the problem would be

$\begin{align} \max_{x} b^Tw \\ s.t.~A^Tw (*)c \end{align}$

where $(*)$ actually depends on the restrictions of the variables in the primal problem. If the restriction is $x_i \geq 0$ then the type of constraint will follow the same inequality. But if $x_i$'s are unrestricted, then the constraints will become $=$

Answer 3

You wrote the dual problem correctly. Perhaps whoever wrote your assignment forgot to include the constraint $x \geq 0$ in the primal problem.

Edit: here's how I derived the dual problem. The Lagrangian is \begin{align} L(x,\nu) &= \langle c, x \rangle + \langle \nu, b - Ax \rangle \\ &= \langle c, x \rangle - \langle \nu, Ax \rangle + \langle \nu, b \rangle \\ &= \langle c, x \rangle - \langle A^T \nu, x \rangle + \langle \nu, b \rangle \\ &= \langle c - A^T \nu, x \rangle + \langle \nu, b \rangle. \end{align}

The dual function is \begin{equation} g(\nu) = \begin{cases} \langle \nu,b \rangle & \quad \text{if } A^T \nu = c \\ -\infty & \quad \text{otherwise}. \end{cases} \end{equation}

So the dual problem is \begin{align} \text{maximize} & \quad \langle \nu, b \rangle \\ \text{subject to} & \quad A^T \nu = c. \end{align}