# Dual of a Linear Program

\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.

-
It looks to me like the form of the dual with the inequality constraint is wrong, and your answer (with the equality constraint) is correct. –  Mike Spivey Nov 26 '12 at 16:40

\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.

-

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 $$g(\nu) = \begin{cases} \langle \nu,b \rangle & \quad \text{if } A^T \nu = c \\ -\infty & \quad \text{otherwise}. \end{cases}$$

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

-
Thanks for the reply. The variable is unconstrained and it was explicitly stated. Can you give a reason why the way i wrote it was correct. –  dineshdileep Nov 26 '12 at 11:19
@dineshdileep I just edited my answer to show how I derived the dual problem. –  littleO Nov 26 '12 at 21:59

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 $=$

-
This is what I also figured. But can you please give an explanation for it... –  dineshdileep Nov 26 '12 at 10:45